×
Schoening, Uwe

A uniform approach to obtain diagonal sets in complexity classes. (English) Zbl 0485.68039

Theor. Comput. Sci. 18, 95-103 (1982).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0485.68039

Cited in 2 Reviews
Cited in 27 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity

Keywords:

sets which diagonalize over certain complexity classes; P; NP; co-NP; PSPACE; APT; almost polynomial time; random polynomial time; polynomial hierarchy
Cite Review PDF
Full Text: DOI

References:

[1] Adleman, L., Two theorems on random polynomial time, Proc. 19th IEEE Symposium on Foundations of Computer Science, 75-83 (1978)
[2] Adleman, L.; Manders, K., Reducibility, randomness, and intractability, Proc. 9th Annual ACM Symposium on Theory of Computing, 151-163 (1977)
[3] Berman, P., Relationship between density and deterministic complexity of NP-complete languages,, (Lecture Notes in Computer Science, 62 (1978), Springer: Springer Berlin), 63-71 · Zbl 0382.68068
[4] Chew, P.; Machtey, M., A note on structure and looking back applied to the relative complexity of computable functions, J. Comput. System. Sci., 22, 53-59 (1981) · Zbl 0474.68063
[5] Cook, S. A., The complexity of theorem proving procedures, Proc. 3rd Annual ACM Symposium on Theory of Computing, 151-158 (1971) · Zbl 0253.68020
[6] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001
[7] Ladner, R. E., On the structure of polynomial time reducibility, J. ACM, 22, 1, 155-171 (1975) · Zbl 0322.68028
[8] Landweber, L. H.; Lipton, R. J.; Robertson, E. L., On the structure of sets in NP and other complexity classes, Theoret. Comput. Sci., 15, 181-200 (1981) · Zbl 0482.68042
[9] T.J. Long, Strong nondeterministic polynomial-time reducibilities, Teor. Comput. Sci; T.J. Long, Strong nondeterministic polynomial-time reducibilities, Teor. Comput. Sci · Zbl 0521.03028
[10] Meyer, A. R.; Paterson, M. S., With what frequency are apparently intractable problems difficult?, (Technical Memo 126 (1979), MIT)
[11] Selman, A. L., P-selective sets, tally languages and the behaviour of polynomial time reducibilities on NP, Math. Systems Theory, 13, 55-65 (1979) · Zbl 0405.03018
[12] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[13] Wrathall, C., Complete sets and the polynomial-time hierarchy, Theoret. Comput. Sci., 3, 23-33 (1977) · Zbl 0366.02031
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.