Name
Abstract | ||
|---|---|---|
this paper we study two different ways to restrict the power of NP: We considerlanguages accepted by nondeterministic polynomial time machines with a small numberof accepting paths in case of acceptance, and also investigate subclasses of NP that arelow for complexity classes not known to be in the polynomial time hierarchy.The first complexity class defined following the idea of bounding the number of acceptingpaths was Valiant's class UP (unique P) [Va76] of languages accepted by... |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1016/0022-0000(92)90022-B | J. Comput. Syst. Sci. |
Keywords | DocType | Volume |
turing machine,low set,complexity class,up,turing machines,complexity classes,polynomial time,languages,computational complexity,polynomials | Conference | 44 |
Issue | ISSN | Citations |
2 | Journal of Computer and System Sciences | 43 |
PageRank | References | Authors |
3.68 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Johannes Köbler | 1 | 580 | 46.51 |
| Uwe Schöning | 2 | 998 | 105.69 |
| Seinosuke Toda | 3 | 608 | 38.63 |
| Jacobo Torán | 4 | 564 | 49.26 |