Reductions on NP and p-selective sets. (English) Zbl 0489.03016

Selman, Alan L.

Theor. Comput. Sci. 19, 287-304 (1982).

MSC:

03D30	Other degrees and reducibilities in computability and recursion theory
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

polynomial time-bounded reducibility; truth-table reducibility; positive query machine; oracle set

References:

[1]	Borodin, A.; Demers, A., Some comments on functional self-reducibility and the NP hierarchy, (Department of Computer Science Technical Report TR76-284 (1976), Cornell University)
[2]	Book, R., Tahy languages and complexity classes, Information and Control, 26, 186-193 (1974) · Zbl 0287.68029
[3]	Book, R.; Wrathall, C.; Selman, A.; Bobkin, D., Inclusion complete tally languages and the Hartmanis-Berman conjecture, Math. Systems Theory, 11, 1-8 (1977) · Zbl 0365.68044
[4]	Jockusch, C., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc., 131, 420-436 (1968) · Zbl 0198.32402
[5]	Cook, S., The complexity of theorem-proving procedures, Proc. 3rd Annual ACM Symposium on Theory of Computing, 151-158 (1971)
[6]	Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 103-123 (1975) · Zbl 0321.68039
[7]	Landweber, L.; Lipton, R.; Robertson, E., On the structure of sets in NP and other complexity classes, Theoret. Comput. Sci., 15, 1-20 (1981) · Zbl 0482.68042
[8]	Long, T., Strong nondeterministic polynomial time reducibilities, Theoret. Comput. Sci., 21, 1-25 (1982) · Zbl 0521.03028
[9]	Meyer, A.; Peterson, M., With what frequency are apparently intractable problems difficult?, M.I.T. Technical Report MIT/LCS/TM-126 (1979)
[10]	Schnorr, C., Optimal algorithms for self-reducible problems, Proc 3rd International Colloquium on Automata, Languages, and Programming (1976), Edinburgh
[11]	Selman, A., P-selective sets, tally languages, and the behavior of polynomial time reducibility on NP, Math. Systems Theory. (Proc. 6th Colloquium on Automata, Languages and Programming. Proc. 6th Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 71 (1979), Springer: Springer Berlin), 13, 55-65 (1979) · Zbl 0405.03018
[12]	Stockmeyer, L., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[13]	Valiant, L., The relative complexity of checking and evaluating, Information Processing Lett., 5, 20-23 (1976) · Zbl 0342.68028
[14]	Wilson, C., Relativization, reducibilities, and the exponential hierarchy, (Department of Computer Science Technical Report 140/80 (1980), University of Toronto)