×

An application of the translational method. (English) Zbl 0794.68056

Summary: We separate \(NE\) from \(P_{n^{0(1)}-T} (NP)\) by using the translational method.

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, R. Beigel, U. Hertrampf, and S. Homer:A Note on the Almost-Everywhere Hierarchy for Nondeterministic Time. Lecture Notes in Computer Science, Vol. 415. Springer-Verlag, Berlin, 1990, pp. 1-11. · Zbl 0729.68022
[2] S. Cook: A Hierarchy for Nondeterministic Time Complexity.J. Comput. System Sci.,7 (1973), 354-375. · Zbl 0284.68038 · doi:10.1016/S0022-0000(73)80029-7
[3] B. Fu, H. Li, and Y. Zhong: Some Properties of Exponential Time Complexity Classes.Proc. 7th IEEE Conference on Structural Complexity Theory, 1992, pp. 50-57.
[4] K. Ganesan and S. Homer: Complete Problems and Strong Polynomial Reducibilities. InTheoretical Aspects of Computer Science. Lecture Notes in Computer Science, Vol. 349. Springer-Verlag, Berlin, 1989, pp. 240-250. · Zbl 0749.68035
[5] J. Hartmanis, P. Lewis, and R. Stearns: Hierarchies of Memory Limited Computations.Proc. 6th IEEE Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 179-190. · Zbl 0229.02033
[6] J. Hartmanis and R. Stearns: On the Computational Complexity of Algorithms.Trans. Amer. Math. Soc.,117 (1965), 285-306. · Zbl 0131.15404 · doi:10.1090/S0002-9947-1965-0170805-7
[7] H. Heller: On Relativized Exponential and Probabilistic Complexity Classes.Inform. and Control,71 (1986), 213-243. · Zbl 0628.68047 · doi:10.1016/S0019-9958(86)80012-2
[8] F. Hennie and R. Stearns: Two-Tape Simulation of Multitape Turing Machine.J. Assoc. Comput. Mach.,13 (1966), 533-546. · Zbl 0148.24801
[9] S. Homer: Structural Properties of Nondeterministic Complete Sets.Proc. 5th IEEE Conference on Structural Complexity Theory, 1990, pp. 3-10.
[10] S. Ruby and P. Fischer: Translational Methods and Computational Complexity.Proc. 6th IEEE Symposium on Switching Circuit Theory and Logical Design, 1965, pp. 173-178. · Zbl 0257.68037
[11] J. Seiferas, M. Fisher, and A. Meyer: Separating Nondeterministic Time Complexity Classes.J. Assoc. Comput. Mach.,25 (1978), 146-167. · Zbl 0366.68038
[12] S. Zak: A Turing Machine Hierarchy.Theoret. Comput. Sci.,26 (1983), 327-333. · Zbl 0525.68026 · doi:10.1016/0304-3975(83)90015-4
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.