Richard E. Ladner
- 1 Axw, POn a subrecursive hierarchy and primitive recurslve degrees Trans. AMS 92 (1959), 85-105Google Scholar
- 2 BORODIN, A, CONSTABLE, R L, ~_ND HOPCROFT, J E Dense and nondense famihes of complexlty classes IEEE Conf Record Tenth Annual Syrup on Swltchang and Automata Theory, 1969, pp. 7-19Google Scholar
- 3 COOK, S A. The complexity of theorem proving procedures. Proc Third Annual ACM Syrup on Theory of Computing, 1971, pp 151-158 Google Scholar
- 4 Fr~I~:DB}~RG, It M Two recurs~vely enumerable sets of incomparable degrees of unsolvablhty. Proc Nat Acad Scz U S A. $3 (1957), 236-238Google Scholar
- 5 GrtZEGORCZYK, A. Some Classes of Rect~rswe Fancl~ons Rozprawy Matematyczhe, Warsaw, 1953Google Scholar
- 6 KARP, R M Reducibility among combinatorial problems In Complexity of Computer Computatwns, R. E Mtller and J. W Thatcher, Eds., Plenum, New York, 1972, pp. 85-103.Google Scholar
- 7 K~aP, R M Private commumcat~on.Google Scholar
- 8 KLEENE, S C , AND POST, E L. The uppersem~-latUce of degrees of unsolvabihty Ann. Math., Ser. 2, 59 (1954), 379-407Google Scholar
- 9 LADSEa, R E, LYNCH, N A, ~NI) SELMAN, A. Comparison of polynomial-t~me reducibilities. Proc S~xth Annual ACM Syrup on Theory of Computing, 1974, pp 110-121 Google Scholar
- 10 LYNCr~, N A. Relat,vizatlon of the theory of computational complexity Tech Rep. TR-99, Project MAC, Ph D. Th, M I.T , Cambridge, Mass., 1972. Google Scholar
- 11 MACUTEY, M. Classification of computable functions by primitive reeurs~ve classes Proc Third Annual ACM Syrup on Theory of Computing, 1971, pp. 251-257 Google Scholar
- 12 M~CHTEY, M Augmented loop languages and classes of computable functions J Comput. Sys~ Sc~. 6, 6 (1972), 603-624Google Scholar
- 13 MACHTEY, M The honest subrecurslve classes are a lattice. I~form and Contr. 24, 3 (1974), 247-263.Google Scholar
- 14 MACHT}.Y, M On the density of honest subrecurstve classes. Tech Rep. CSD TR 92, Comput. Sc~. Dep, Purdue U., Lafayette, Ind, 1973Google Scholar
- 15 MEYER, A R , AND R~TCHIL, D M A classification of the recursLve functmns Z Math Log~k Grul~dlagen Math 18 (1972), 71-82Google Scholar
- 16 MEYER, A R Private commumcatmnGoogle Scholar
- 17 MUCHNIK, A A On the unsolvabillty of the problem of reducibfilty m the theory of algorithms. Doklady Akadcm~ Navk SSSR, n s , 108 (1956), 194-197Google Scholar
- 18 PosT, E. L Recurslvely enumerable sets of posttlve integers and their decision problems. bull. AMS 50 (1944), 284-316Google Scholar
- 19 Pi~ iTT, V Every prime has a succinct certificate (In preparation )Google Scholar
- 20 RITCHIE, R W Classes of predictably computable functions Trans AMS 106 (1963), 139-173.Google Scholar
- 21 RoGrms Ji~, H Theory of Recurszve Funchons a~d Effective Computab~.hty McGraw-Hill, New York, 1967Google Scholar
- 22 Sr.TnI, R Complete register allocation problems Proc Fifth Annual ACM Syrup on Theory of Computing, 1973, pp 183-195 Google Scholar
- 23 STOCKMEYER, L J Planar 3-colorabihty is polynomial complete. SIGACT News 5, 3 (1973), 19-25 Google Scholar
- 24 STOCKMEYER, L. J , AND MEYER, A R Word problems requiring exponential ttme preliminary report Proc Fifth Annual ACM Syrup on Theory of Computing, 1973, pp 1-9 Google Scholar
- 25 ULL~t tN, J D Polynomial complete scheduling problems ACM Operating Syst Reo 7, 4 (1973), Fourth Symposium on Operating System Principles, 96-101 Google Scholar
Index Terms
- On the Structure of Polynomial Time Reducibility
Recommendations
Enumeration reducibility with polynomial time bounds
CiE'06: Proceedings of the Second conference on Computability in Europe: logical Approaches to Computational BarriersWe introduce polynomial time enumeration reducibility (≤pe) and we retrace Selman's analysis of this reducibility and its relationship with non deterministic polynomial time conjunctive reducibility. We discuss the basic properties of the degree ...
Comments