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


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


[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)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.