[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 |