Abstract
We study certain language classes located between P and NP that are defined by polynomial time machines with bounded amount of nondeterminism. We observe that these classes have complete problems, and find characterizations of the classes using robust machines with bounded access to the oracle, and in terms of nondeterministic complexity classes with polylog running time. We also study the relationship of these classes to P and NP.
The research of this author was supported by CIRIT grant EE87/2
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Adleman: Time, Space and Randomness. Tech Report MIT/LCS/TM-131, MIT 1979.
E. Allender: Invertible functions. Ph.D. dissertation, Georgia Institute of Technology, 1985.
I. Baker, J. Gill, R. Solvay: 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) 1988, Springer-Verlag.
P. Berman: Relationships between density and deterministic complexity of NP-complete languages. Proceedings 5th ICALP, 1978, 63–72.
R. Book: Tally languages and complexity classes. Information and Control, 1974, 186–193.
J. Cai, L. Hemachandra: On the power of parity. Symp. Theor. Aspects of Comput. Sci. 1989, 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. 13th. ICALP, 1986, 123–135.
J. Hartmanis, L. Hemachandra: One-way functions, robustness, and the nonisomorphism of NP-complete sets. 2nd Structure in Complexity Theory Conference, 1987, 160–175.
L. Hemachandra, G. Wechsung: Using randomness to characterize the complexity of computation. To appear in IFIP 89.
R. Impagliazzo, M. Naor: Decision Trees and Downward Closures. 3rd. Structure in Complexity Theory Conference, 1988, 29–38.
N. Jones, W. Laaser: Complete problems for deterministic polynomial time. Theoretical Computer Science, 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. Theoretical Computer Science, 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. To appear in 4th Structure in Complexity Theory Conference, 1989.
R. Ladner: On the structure of polynomial time reducibility. J.ACM, 22 1975, 155–171.
S. Mahaney: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. In Proceedings IEEE Symposium on Foundations of Computer Science, 1980, 54–60.
U. Schöning, R. Book: Immunity, relativizations, and nondeterminism. SIAM J. Comput., 9, 1984, 46–53.
U. Schöning: Robust algorithms: a different approach to oracles. Theoretical Computer Science, 40, 1985, 57–66.
U. Schöning: Complexity and Structure. Lecture Notes in Computer Science, 1986, Springer-Verlag.
U. Schöning: Robust oracle machines. Proceedings 13th Math. Fundations of Computer Science, 1988, 93–107.
L. Valiant: Relative complexity of checking and evaluating. Information Processing Letters, 5, 1976, 20–23.
M. Xu, J. Doner, R. Book: Refining nondeterminism in relativizations of complexity classes. JACM 30, 1983, 677–685.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Àlvarez, C., Díaz, J., Torán, J. (1989). Complexity classes with complete problems between P and NP-C. In: Csirik, J., Demetrovics, J., Gécseg, F. (eds) Fundamentals of Computation Theory. FCT 1989. Lecture Notes in Computer Science, vol 380. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51498-8_2
Download citation
DOI: https://doi.org/10.1007/3-540-51498-8_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51498-5
Online ISBN: 978-3-540-48180-5
eBook Packages: Springer Book Archive