On self-reducibility and weak P-selectivity. (English) Zbl 0519.68062

Ko, Ker-I

J. Comput. Syst. Sci. 26, 209-221 (1983).

MSC:

68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68Q25	Analysis of algorithms and problem complexity
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

NP; self-reducibility; lowness; P-selective sets; left Dedekind cuts; polynomial-time m-completeness; polynomial-time T-completeness

Citations:

Zbl 0415.03031; Zbl 0486.03020

References:

[1]	Adleman, L., Two theorems on random polynomial time, (Proceedings, 19th IEEE Symposium on Foundations of Computer Science (1978)), 75-83
[2]	Bennett, C. H.; Gill, J., Relative to a random oracle \(A, P^A\) ≠ \(NP^A\) ≠ co-\(NP^A\) with probability 1, SIAM J. Comput., 10, 96-113 (1981) · Zbl 0454.68030
[3]	Bennison, V. L., Some lowness properties and computational complexity sequences, Theoret. Comput. Cci., 6, 233-254 (1978) · Zbl 0401.68021
[4]	Bennison, V. L., Information content characterizations of complexity theoretic properties, (Proceedings, 4th GI Conference on Theoretical Computer Science. Proceedings, 4th GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science, No. 67 (1979), Springer-Verlag: Springer-Verlag Berlin/New York), 58-66 · Zbl 0401.68022
[5]	Berman, L., On the structure of complete sets: Almost everywhere complexity and infinitely often speed up, (Proceedings, 17th Symposium on Foundations of Computer Science (1976)), 76-80
[6]	Berman, P., Relationship between density and deterministic complexity of NP-complete languages, (Proceedings, 5th International Colloquium Automata, Languages and Programming. Proceedings, 5th International Colloquium Automata, Languages and Programming, Lecture notes in Computer Science, No. 62 (1978), Springer-Verlag: Springer-Verlag Berlin/New York), 63-71
[7]	Berman, L.; Hartmanis, J., On isomorphism and densities of NP and other complete sets, SIAM J. Comput., 6, 305-322 (1977) · Zbl 0356.68059
[8]	Cook, S. A., The complexity of theorem-proving procedures, (Proceedings, 3rd ACM Symposium on Theory of Computing (1971)), 151-158 · Zbl 0363.68125
[9]	Fortune, S., A note on sparse complete sets, SIAM J. Comput., 8, 431-433 (1979) · Zbl 0415.68006
[10]	Karp, R.; Lipton, R., Some connections between nonuniform and uniform complexity classes, (Proceedings, 12th ACM Symposium on Theory of Computing (1980)), 302-309
[11]	Ko, K., The maximum value problem and NP real numbers, J. Comput. System Sci., 24, 15-35 (1982) · Zbl 0481.03038
[13]	Ko, K.; Moore, D. J., Completeness, approximation and density, SIAM J. Comput., 10, 787-796 (1981) · Zbl 0468.68051
[14]	Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 103-213 (1975) · Zbl 0321.68039
[15]	Mahaney, S. R., Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis, (Proceedings, 21st IEEE Symposium on Foundations of Computer Science (1980)), 54-60
[16]	Meyer, A.; Paterson, M., With What Frequency Are Apparently Intractable Problem Difficult?, MIT Tech. Rep., MIT/LES/TM-126 (1979)
[17]	Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
[19]	Selman, A. L., \(P\)-selective sets, tally languages and the behavior of polynomial time reducibilities on NP, Math. Systems Teory, 13, 55-65 (1979) · Zbl 0405.03018
[20]	Selman, A. L., Some observations on NP real numbers and \(p\)-selective sets, J. Comput. System Sci., 23, 326-332 (1981) · Zbl 0486.03020
[21]	Selman, A. L., Reductions on NP and p-selective sets, Theoret. Comput. Sci., 19, 287-304 (1982) · Zbl 0489.03016
[22]	Scare, R. I., Computational complexity, speedable and levelable sets, J. Symbolic Logic, 42, 545-563 (1977) · Zbl 0401.68020
[23]	Stockmeyer, L. J.; Meyer, A. R., Word problems requiring exponential time, (Proceedings, 5th ACM Symposium on Theory of Computing (1973)), 1-9 · Zbl 0359.68050