Three theorems on polynomial degrees of NP-sets
- 1 January 1985
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We show that recursive ascending sequences of polynomial time (p-) degrees do not possess minimal upper bounds; that, for every nonzero p-degree a, there is a lesser nonzero p-degree b which does not help a; and that every nonzero p-degree is half of a minimal pair.Keywords
This publication has 18 references indexed in Scilit:
- Minimal pairs for PTheoretical Computer Science, 1984
- On the complement of one complexity class in anotherPublished by Springer Nature ,1984
- A note on a theorem by LadnerInformation Processing Letters, 1982
- A uniform approach to obtain diagonal sets in complexity classesTheoretical Computer Science, 1982
- On the structure of sets in NP and other complexity classesTheoretical Computer Science, 1981
- The polynomial-time hierarchyTheoretical Computer Science, 1976
- Polynomial and abstract subrecursive classesJournal of Computer and System Sciences, 1976
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Sets that don't helpPublished by Association for Computing Machinery (ACM) ,1973
- Polynominal time reducibilityPublished by Association for Computing Machinery (ACM) ,1973