Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
Author:
- Alan L. SelmanASAlan L. Selman
- 1 January 1982
- journal article
- Published by Elsevier in Information and Control
- Vol. 52 (1) , 36-51
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
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Comparing complexity classesJournal of Computer and System Sciences, 1974
- Tally languages and complexity classesInformation and Control, 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