Sublattices of the polynomial time degrees

Information and Control - Tập 65 - Trang 63-84 - 1985
Klaus Ambos-Spies1
1Lehrstuhl für Informatik II, Universität Dortmund, Dortmund, West Germany

Tài liệu tham khảo

Ambos-Spies, 1984, On the structure of polynomial time degrees, Vol. 166, 198 Ambos-Spies, 1984, P-mitotic sets, Vol. 171, 1 Ambos-Spies, 1986, Polynomial time degrees of NP-sets Ambos-Spies, K. (to appear), An inhomogeneity in the structure of Karp degrees, SIAM J. Computing. Balcazar, 1982, A note on a theorem by Ladner, Inform. Process. Lett., 15, 84, 10.1016/0020-0190(82)90113-2 Breidbart, 1978, On splitting recursive sets, J. Comput. System Sci., 17, 56, 10.1016/0022-0000(78)90034-X Chew, 1981, A note on structure and looking back applied to the relative complexity of computable functions, J. Comput. System Sci., 22, 53, 10.1016/0022-0000(81)90021-0 Cook, 1971, The complexity of theorem proving procedures, 151 Even, 1982, A note on deterministic and nondeterministic time complexity, Inform. and Control, 55, 117, 10.1016/S0019-9958(82)90515-0 Grätzer, 1978 Karp, 1972, Reducibility among combinatorial problems, 85 Ladner, 1973, Polynomial time reducibility, 122 Ladner, 1975, On the structure of polynomial time reducibility, J. Assoc. Comput. Mach., 22, 155, 10.1145/321864.321877 Ladner, 1975, A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 103, 10.1016/0304-3975(75)90016-X Landweber, 1981, On the structure of sets in NP and other complexity classes, Theoret. Comput. Sci., 15, 181, 10.1016/0304-3975(81)90069-4 Mehlhorn, 1974, The “almost all” theory of subrecursive degrees is decidable, Vol. 15, 317 Mehlhorn, 1976, Polynomial and abstract subrecursive classes, J. Comput. System Sci., 12, 147, 10.1016/S0022-0000(76)80035-9 Regan, 1983, On diagonalization methods and the structure of language classes, Vol. 158, 368 Schmidt, 1984, ON the complement of one complexity class in another, Vol. 171, 77 Schöning, 1982, A uniform approach to obtain diagonal sets in complexity classes, Theoret. Comput. Sci., 18, 95, 10.1016/0304-3975(82)90114-1 Schöning, 1982, On NP-decomposable sets, SIGACT Newsletter, 14, 18, 10.1145/1008892.1008893 Schöning, 1983, On the structure of Δp2, Inform. Process. Lett., 16, 209, 10.1016/0020-0190(83)90126-6 Schöning, 1984, Minimal pairs for P, Theoret. Comput. Sci., 31, 41, 10.1016/0304-3975(84)90124-5