On the Structure of Polynomial Time Reducibility
- 1 January 1975
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 22 (1), 155-171
- https://doi.org/10.1145/321864.321877
Abstract
No abstract availableThis publication has 10 references indexed in Scilit:
- Planar 3-colorability is polynomial completeACM SIGACT News, 1973
- Complete register allocation problemsPublished by Association for Computing Machinery (ACM) ,1973
- Word problems requiring exponential time(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1973
- A Classification of the Recursive FunctionsMathematical Logic Quarterly, 1972
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- Classification of computable functions by primitive recursive classesPublished by Association for Computing Machinery (ACM) ,1971
- Dense and non-dense families of complexity classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1969
- Classes of predictably computable functionsTransactions of the American Mathematical Society, 1963
- On a subrecursive hierarchy and primitive recursive degreesTransactions of the American Mathematical Society, 1959
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)Proceedings of the National Academy of Sciences, 1957