Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- 31 January 1982
- journal article
- Published by Elsevier in Information and Control
- Vol. 52 (1) , 36-51
- https://doi.org/10.1016/s0019-9958(82)80084-3
Abstract
No abstract availableThis publication has 17 references indexed in Scilit:
- On the definitions of some complexity classes of real numbersTheory of Computing Systems, 1983
- The maximum value problem and NP real numbersJournal of Computer and System Sciences, 1982
- On splitting recursive setsJournal of Computer and System Sciences, 1978
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Tally languages and complexity classesInformation and Control, 1974
- Comparing complexity classesJournal of Computer and System Sciences, 1974
- Turing machines and the spectra of first-order formulasThe Journal of Symbolic Logic, 1974
- Semirecursive sets and positive reducibilityTransactions of the American Mathematical Society, 1968