A comparison of polynomial time completeness notions. (English) Zbl 0635.68035

Watanabe, Osamu

Theor. Comput. Sci. 54, 249-265 (1987).

Several types of polynomial time reductions for the superpolynomial decision problem class \(DEXT=\cup \{DTIME(2^{cn})|\) \(c>0\}\) are considered. The purpose of the paper is to characterize the differences between polynomial time completeness notions for DEXT with respect to any pair of the above reductions. The author succeeds to prove all but two differences for the class DEXT. An interesting open problem is whether or not the obtained results hold also for complexity classes specified by nondeterministic machines.

Reviewer: J.Błażewicz

MSC:

68Q25

Analysis of algorithms and problem complexity

Keywords:

polynomial time transformation; superpolynomial deterministic classes; polynomial time reductions; superpolynomial decision problem class; completeness; complexity classes

References:

[1]	Baker, T.; Gill, J.; Solvay, R., Relativizations of the \(P\)=?NP question, SIAM J. Comput., 4, 4, 431-442 (1975) · Zbl 0323.68033
[2]	Balcázar, J.; Schöning, U., Bi-immune sets for complexity classes, Math. Systems Theory, 18, 1-10 (1985) · Zbl 0572.68035
[3]	Bennet, C.; Gill, J., Relative to a random oracle \(A, P^A\) ≠ \(NP^A\) ≠ co-\(NP^A\) with probability 1, SIAM J. Comput., 10, 96-113 (1981) · Zbl 0454.68030
[4]	Berman, L., On the structure of complete sets, (Proc. 17th FOCS (1976)), 76-80
[5]	Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. Comput., 6, 2, 305-322 (1977) · Zbl 0356.68059
[6]	Book, R.; Long, T.; Selman, A., Qualitative relativizations of complexity classes, J. Comput. System Sci., 30, 395-413 (1985) · Zbl 0569.03016
[7]	Cook, S., The complexity of theorem proving procedures, (Proc. 3rd STOC (1971)), 151-158 · Zbl 0253.68020
[8]	Hartmanis, J., Feasible Computations and Provable Complexity Properties (1978), SIAM: SIAM Philadelphia, PA · Zbl 0383.68043
[9]	Hartmanis, J., Generalized Kolmogorov complexity and the structure of feasible computations, (Proc. 24th FOCS (1983)), 439-445
[10]	Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Language, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[11]	Karp, R.; Lipton, R., Some connections between non-uniform and uniform complexity classes, (Proc. 12th STOC (1980)), 302-309
[12]	Ko, K.; Moore, D., Completeness, approximation and density, SIAM J. Comput., 10, 787-796 (1981) · Zbl 0468.68051
[13]	Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. Comput Sci., 1, 103-123 (1975) · Zbl 0321.68039
[14]	Mahaney, S., Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, J. Comput. System Sci., 25, 130-143 (1982) · Zbl 0493.68043
[15]	Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
[16]	Watanabe, O., On one-one polynomial time equivalence relations, Theoret. Comput. Sci., 38, 157-165 (1985) · Zbl 0582.68016
[17]	Young, P., Some structural properties of polynomial reducibilities, Proc. 15th STOC, 392-401 (1983)