Sublattices of the polynomial time degrees
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