Title :
Three theorems on polynomial degrees of NP-sets
Author :
Ambos-Spies, Klaus
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 :
Helium; Lattices; NP-complete problem; Polynomials; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1985., 26th Annual Symposium on
Conference_Location :
Portland, OR, USA
Print_ISBN :
0-8186-0644-4
DOI :
10.1109/SFCS.1985.61