Completeness for nondeterministic complexity classes. (English) Zbl 0745.68046

Buhrman, Harry; Homer, Steven; Torenvliet, Leen

Math. Syst. Theory 24, No. 3, 179-200 (1991).

Summary: We demonstrate differences between reducibilities and corresponding completeness notions for nondeterministic time and space classes. For time classes the studied completeness notions under polynomial-time bounded (even logarithmic-space bounded) reducibilities turn out to be different for any class containing \(NE\). For space classes the completeness notions under logspace reducibilities can be separated for any class properly containing LOGSPACE. Key observation in obtaining the separations is the honesty property of reductions, which was recently observed to hold for the time classes and can be shown to holds for space classes.

MSC:

68Q15

Complexity classes (hierarchies, relations among complexity classes, etc.)

Keywords:

reducibilities; completeness; nondeterministic time and space classes

References:

[1]	Balcázar J. L., J. Díaz, and J. Gabarró. Structural complexity I. (W. Brauer, G, Rozenberg, and A, Salomaa, eds.). EATCS Monographs on Theoretical Computer Science, Vol. 11. Springer-Verlag, New York, 1988.
[2]	Berman L. On the structure of complete sets.Proc. 17th IEEE Conference on Foundations of Computer Science, 1976, pp. 76–80.
[3]	Berman L., and J. Hartmanis. On isomorphisms and density ofNP and other complete sets.SIAM J. Comput. 1 (1977), 305–322. · Zbl 0356.68059 · doi:10.1137/0206023
[4]	Cook, S. A. The complexity of theorem-proving procedures.Proc. Third ACM Symposium on Theory of Computing, 1971, pp. 151–158. · Zbl 0253.68020
[5]	Ganesan K. and S. Homer. Complete Problems and Strong Polynomial Reducibilities. Technical Report #88-001, Boston University, January 1988. Also inAspects of Computer Science. Lecture Notes in Computer Science, Vol. 349. Springer-Verlag, Berlin, 1989, pp. 240–250.
[6]	Hartmanis J.Feasible Computations and Provable Complexity Properties. NSF Regional Conference Series in Applied Mathematics, 1978. · Zbl 0383.68043
[7]	Hartmanis J. On the logtape isomorphism of complete sets.Theoret. Comput. Sci. 7 (1978), 273–286. · Zbl 0387.68035 · doi:10.1016/0304-3975(78)90018-X
[8]	Immerman N. Nondeterministic space is closed under complementation.SIAM J. Comput. 17 (1988), 935–938. · Zbl 0668.68056 · doi:10.1137/0217058
[9]	Jones N. Space bounded reducibilities among combinatorial problems.J. Comput. System Sci. 11 (1975), 68–85. · Zbl 0317.02039 · doi:10.1016/S0022-0000(75)80050-X
[10]	Karp R. M. Reducibility among combinatorial problems. InComplexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum, New York, pp. 85–103. · Zbl 0366.68041
[11]	Ladner R. and N. Lynch. Relativizations of questions about log space computability.Math. Systems Theory 10 (1975), 19–32. · Zbl 0341.68036 · doi:10.1007/BF01683260
[12]	Ladner R. E., N. Lynch, and A. L. Selman. A comparison of polynomial time reducibilities.Theoret. Comput. Sci. 1 (1975), 103–123. · Zbl 0321.68039 · doi:10.1016/0304-3975(75)90016-X
[13]	Russo D. Optimal approximations of complete sets.Proc. Structure in Complexity Theory Conference, 1986. Lecture Notes in Computer Science, Vol. 223, Springer-Verlag, Berlin, 1986, pp. 311–324. · Zbl 0633.03035
[14]	Szelepcsényi R. The method of forcing for nondeterministic automata.Bull. EATCS 33 (1987), 96–100. · Zbl 0664.68082
[15]	Watanabe O. A comparison of polynomial time completeness notions.Theoret. Comput. Sci. 54 (1987), 249–265. · Zbl 0635.68035 · doi:10.1016/0304-3975(87)90132-0
[16]	Watanabe O. On the Structure of Intractable Complexity Classes. Ph.D. thesis, Department of Computer Science, Tokyo Institute of Technology, 1987.