Reductions on NP and P-selective sets
- 30 September 1982
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 19 (3) , 287-304
- https://doi.org/10.1016/0304-3975(82)90039-1
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Strong nondeterministic polynomial-time reducibilitiesTheoretical Computer Science, 1982
- On the structure of sets in NP and other complexity classesTheoretical Computer Science, 1981
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNPTheory of Computing Systems, 1979
- Inclusion complete tally languages and the Hartmanis-Berman conjectureTheory of Computing Systems, 1977
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Relative complexity of checking and evaluatingInformation Processing Letters, 1976
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- Tally languages and complexity classesInformation and Control, 1974
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Semirecursive sets and positive reducibilityTransactions of the American Mathematical Society, 1968