On reductions of NP sets to sparse sets. (English) Zbl 0806.68046

Homer, Steven; Longpré, Luc

J. Comput. Syst. Sci. 48, No. 2, 324-336 (1994).

Summary: Ogiwara and Watanabe showed that if SAT is bounded truth-table reducible to a sparse set, then P = NP. In this paper we simplify their proof, strengthen the result and use it to obtain several new results. Among the new results are the following:
\(\bullet\) Applications of the main theorem to log-truth-table and log- Turing reductions of NP sets to sparse sets. One typical example is that if SAT is log-truth-table reducible to a sparse set then NP is contained in DTIME \((2^{O(\log^ 2 n)})\).
\(\bullet\) Generalizations of the main theorem which yields results similar to the main result at arbitrary levels of the polynomial hierarchy and which extend as well to strong nondeterministic reductions.
\(\bullet\) The construction of an oracle relative to which \(\text{P} \neq \text{NP}\) but there are NP-complete sets which are \(f(n)\)-tt-reducible to a tally set, for any \(f(n) \in \omega(\log n)\). This implies that, up to relativization, some of our results are optimal.

MSC:

68Q15

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

References:

[1]	Arvind, V.; Han, Y.; Hemachandra, L.; Köbler, J.; Lozano, A.; Mundhenk, M.; Ogiwara, M.; Schöning, U.; Silvestri, R.; Thierauf, T., Reductions to Sets of Low Information Content, (Complexity Theory: Current Research (1993), Cambridge Univ. Press), 1-46 · Zbl 0794.68058
[2]	Grollmann, J.; Selman, A., Complexity measures for public-key cryptosystems, SIAM J. Comput., 11, 309-335 (1988) · Zbl 0644.94016
[3]	Kadin, J., \(P^{NP[log n]}\) and sparse Turing-complete sets for NP, J. Comput. System Sci., 39, 282-298 (1989) · Zbl 0693.68027
[4]	Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (Proceedings 12th ACM Symp. on Theory of Computing (1980)), 302-309
[5]	Karp, R.; Lipton, R., Turing machines that take advice, Enseign. Math., 28, 191-209 (1982) · Zbl 0529.68025
[6]	Long, T., Strong nondeterministic polynomial-time reducibilities, Theoret. Comput. Sci., 21, 1-25 (1982) · Zbl 0521.03028
[7]	Long, T., On restricting the size of oracles compared with restricting access to oracles, SIAM J. Comput., 14, No. 3, 585-597 (1985) · Zbl 0583.68025
[8]	Longpré, L., Resource Bounded Kolmogorov Complexity, a Link between Computational Complexity and Information Theory, (Ph.D. thesis (1986), Cornell University), Technical Report TR86-776
[9]	Li, M.; Vitányi, P. M.B., An Introduction to Kolmogorov Complexity and its Applications (1993), Springer-Verlag
[10]	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
[11]	Ogiwara, M.; Lozano, A., On one query self-reducible sets, (Proceedings, Structure in Complexity Theory Sixth Annual Conference (1991), IEEE Computer Society Press), 139-151
[12]	Ogiwara, M.; Watanabe, O., On polynomial time bounded truth-table reducibility of NP sets to sparse sets, (Proceedings 22nd Annual ACM Symposium on Theory of Computing (1990)), 457-467