×

Limitations of the upward separation technique. (English) Zbl 0708.68019

The prototype of a result proven by use of the upward separation technique is Hartmanis’ result stating that \(E=NE\) iff there exists no sparse set in NP-P. The author investigates the strength of this method.
It was claimed by Hartmanis that his technique would entail the following generalization for doubly exponential time classes: \(EE=NEE\) iff there exists no supersparse set in NP-P; this result however can not be shown using the upward separation method. The author has shown that the conclusion fails in some relativised world, whereas the upward separation technique does relativise. The oracle construction used in the proof has an original flavour; rather than alternating between encoding and diagonalization stages all encoding is performed already at the start; the “there is room to diagonalize” part of the proof is based on a Kolmogorov complexity argument, thus getting rid of all combinatorics.
Having thus established a result where the method doesn’t generalize the author completes his investigations by showing results where the method does work. They primarily involve the separation of deterministic and nondeterministic time classes with timebounds inbetween single and doubly exponential time and the existence of sets in NP-P of specific density or generalized Kolmogorov complexity.
Reviewer: P.van Emde-Boas

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Allender, The complexity of sparse sets inP, Proc. 1st Structure in Complexity Theory Conference, Lecture Notes in Computer Science, Vol. 223, Springer-Verlag, Berlin, 1986, pp. 1–11.
[2] E. Allender, The generalized Kolmogorov complexity of sets,Proc. 4th Structure in Complexity Theory Conference, 1989, pp. 186–194.
[3] E. Allender, Limitations of the upward separation technique,Proc. 16th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 372, Springer-Verlag, Berlin, 1989, pp. 18–30.
[4] E. Allender and R. Rubinstein,P-printable sets,SIAM Journal on Computing,17 (1988), 1193–1202. · Zbl 0682.68039 · doi:10.1137/0217075
[5] E. Allender and C. Wilson, Downward translations of equality, to appear inTheoretical Computer Science. · Zbl 0701.68027
[6] J. Balcázar, J. Díaz, and J. Gabarró,Structural Complexity, Vol. I, Springer-Verlag, Berlin, 1988. · Zbl 0638.68040
[7] R. Beigel, On the relativized power of additional accepting paths,Proc. 4th Structure in Complexity Theory Conference, 1989, pp. 216–224.
[8] A. Blass and Y. Gurevich, On the unique satisfiability problem,Information and Control,55 (1982), 80–88. · Zbl 0543.03027 · doi:10.1016/S0019-9958(82)90439-9
[9] R. Book, Tally languages and complexity classes,Information and Control,26 (1974), 186–193. · Zbl 0287.68029 · doi:10.1016/S0019-9958(74)90473-2
[10] R. Book, C. Wilson, and Xu Mei-Rui, Relativizing time, space, and time-space,SIAM Journal on Computing,11 (1982), 571–581. · Zbl 0487.68038 · doi:10.1137/0211048
[11] J. Cai and L. Hemachandra, On the power of parity polynomial time,Proc. 6th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 349, Springer-Verlag, Berlin, 1989, pp. 229–239.
[12] M. Dekhtyar, On the relativization of deterministic and nondeterministic complexity classes,Proc. 5th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 45, Springer-Verlag, Berlin, 1976, pp. 255–259. · Zbl 0339.68039
[13] R. Gavaldà, L. Torenvliet, O. Watanabe, and J. Balcázar, Generalized Kolmogorov complexity in relativized separations,Proc. 15th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 452, Springer-Verlag, Berlin, 1990, pp. 269–276. · Zbl 0825.68428
[14] J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations,Proc. 24th IEEE Symposium on Foundations of Computer Science, 1983, pp. 439–445.
[15] J. Hartmanis, On sparse sets inNP-P, Information Processing Letters,16 (1983), 55–60. · Zbl 0501.68014 · doi:10.1016/0020-0190(83)90024-8
[16] J. Hartmanis, N. Immerman, and V. Sewelson. Sparse sets inNP-P: EXPTIME versus NEXPTIME,Information and Control,65 (1985), 158–181. · Zbl 0586.68042 · doi:10.1016/S0019-9958(85)80004-8
[17] H. Heller, On relativized exponential and probabilistic complexity classes,Information and Control,71 (1986), 231–243. · Zbl 0628.68047 · doi:10.1016/S0019-9958(86)80012-2
[18] J. Hopcroft and J. Ullman,Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Massachusetts, 1979. · Zbl 0426.68001
[19] R. Impagliazzo and G. Tardos Decision versus search in super-polynomial time,Proc. 30th Annual IEEE Symposium on Foundations of Computer Science, (1989), pp. 222–227.
[20] J. Köbler, U. Schoning, S. Toda, and J. Torán, Turing machines with few accepting computations and low sets for PP,Proc. 4th Structure in Complexity Theory Conference, 1989, pp. 208–215.
[21] S. Kurtz, Sparse sets inNP-P: relativizations,SIAM Journal on Computing,14 (1985), 113–119. · Zbl 0574.03020 · doi:10.1137/0214008
[22] G. Lischke, Oracle-constructions to prove all possible relationships between relativizations ofP, NP, EL, NEL, EP andNEP, Zeitschrift für mathematische Logic und Grundlagen der Mathematik,32 (1986), 257–270. · Zbl 0594.68045 · doi:10.1002/malq.19860321702
[23] G. Lischke, Relativizations ofNP andEL, strongly separating, and sparse sets,J. Information Processing and Cybernetics EIK,23 (1987), 99–112. · Zbl 0578.68037
[24] Ming Li and P. Vitányi, Two decades of applied Kolmogorov complexity,Proc. 3rd Structure in Complexity Theory Conference, 1988, pp. 80–101.
[25] W. Paul, On-line simulation ofk + 1 tapes byk tapes requires nonlinear time,Information and Control,53 (1982), 1–8. · Zbl 0536.68049 · doi:10.1016/S0019-9958(82)91055-5
[26] R. Rubinstein, Structural Complexity Classes of Sparse Sets: Intractability, Data Compression and Printability, Doctoral dissertation, Northeastern University, 1988.
[27] U. Schöning,Complexity and Structure, Lecture Notes in Computer Science, Vol. 211, Springer-Verlag, Berlin, 1985.
[28] O. Watanabe, On hardness of one-way functions,Information Processing Letters,27 (1988), 151–157. · Zbl 0635.68037 · doi:10.1016/0020-0190(88)90071-3
[29] C. Wilson, Relativization, Reducibilities and the Exponential Hierarchy, M.S. thesis, University of Toronto, 1980.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.