Name
Abstract | ||
|---|---|---|
We study certain language classes located betweenP andNP that are defined by polynomial-time machines with a bounded amount of nondeterminism. We observe that these classes have complete problems and find a characterization of the classes using robust machines with bounded access to the oracle, obtaining some other results in this direction. We also study questions related to the existence of complete tally sets in these classes and closure of the classes under different types of polynomial-time reducibilities. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1007/BF02090764 | Mathematical Systems Theory |
Keywords | DocType | Volume |
Computational Mathematic,Complete Problem,Language Class,Robust Machine,Complete Tally | Journal | 23 |
Issue | ISSN | Citations |
1 | 1433-0490 | 34 |
PageRank | References | Authors |
2.91 | 12 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 141 | 13.56 |
| Jacobo Torán | 2 | 564 | 49.26 |