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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
L. Aldeman: Time, space and randomness. Technical Report MIT/LCS/TM-131, Massachusetts Institute of Technology, 1979.
E. Allender: Invertible functions. Ph.D. dissertation, Georgia Institute of Technology, 1985.
I. Baker, J. Gill, R. Solovay: Relativization of the P=?NP question.SIAM J. Comput.,4, 1975, 431–442.
J. L. Balcázar: En torno a oraculos que ciertas maquinas consultan, y las espantables consecuencias a que ello da lugar. Ph.D. Dissertation, FIB, 1984.
J. L. Balcázar, J. Diaz, J. Gabarró:Structural Complexity, Vol. 1. Springer-Verlag, Berlin, 1988.
P. Berman: Relationships between density and deterministic complexity of NP-complete languages.Proc. 5th ICALP, 1978, pp. 63–72.
R. Book: Tally languages and complexity classes.Inform. and Control, 1974, 186–193.
S. Buss: The boolean formula value problem is in ALOGTIME.Proc. 19th STOC, 1987, pp. 123–131.
J. Cai, L. Hemachandra: On the power of parity.Proc. Symp. Theory of Aspects of Computer Science, 1989, pp. 229–240.
J. Gill: Computational complexity of probabilistic Turing machines.SIAM J. Comput.,6, 1977, 675–695.
J. Hartmanis, L. Hemachandra: Complexity classes without machines: on complete languages for UP.Proc. 13th ICALP, 1986, pp. 123–135.
J. Hartmanis, L. Hemachandra: One-way functions, robustness, and the nonisomorphism ofNP-complete sets.Proc. 2nd Structure in Complexity Theory Conf., 1987, pp. 160–175.
L. Hemachandra, G. Wechsung: Using randomness to characterize the complexity of computation.Proc. IFIP, 1989, to appear.
N. Jones, W. Laaser: Complete problems for deterministic polynomial time.Theoret. Comput. Sci.,3, 1976, 105–118.
C. Kintala, P. Fisher: Refining nondeterminism in relativized complexity classes.SIAM J. Comput.,13, 1984, 329–337.
K. Ko: On helping by robust oracle machines.Theoret. Computer Sci.,52, 1987, 15–36.
J. Köbler, U. Schöning, S. Toda, J. Torán: Turing machines with few accepting computations and low sets for PP.Proc. 4th Structure in Complexity Theory Conf., 1989, pp. 208–216.
R. Ladner: On the structure of polynomial time reducibility.J. Assoc. Comput. Mach.,22, 1975, 155–171.
S. Mahaney: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis.Proc. IEEE Symp. on Foundations of Computer Science, 1980, pp. 54–60.
U. Schöning: Robust algorithms: a different approach to oracles.Theoret. Comput. Sci.,40, 1985, 57–66.
U. Schöning:Complexity and Structure. Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1986.
U. Schöning, R. Book: Immunity, relativizations, and nondeterminism.SIAM J. Comput.,9, 1984, 46–53.
L. Valiant: Relative complexity of checking and evaluating.Inform. Process. Lett.,5, 1976, 20–23.
M. Xu, J. Doner, R. Book: Refining nondeterminism in relativizations of complexity classes.J. Assoc. Comput. Mach.,30, 1983, 677–685.
Author information
Authors and Affiliations
Additional information
The research of this author was supported by CIRIT Grant EE87/2.
Rights and permissions
About this article
Cite this article
Díaz, J., Torán, J. Classes of bounded nondeterminism. Math. Systems Theory 23, 21–32 (1990). https://doi.org/10.1007/BF02090764
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02090764