DocumentCode :
2182691
Title :
Three theorems on polynomial degrees of NP-sets
Author :
Ambos-Spies, Klaus
fYear :
1985
fDate :
21-23 Oct. 1985
Firstpage :
51
Lastpage :
55
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1985., 26th Annual Symposium on
Conference_Location :
Portland, OR, USA
ISSN :
0272-5428
Print_ISBN :
0-8186-0644-4
Type :
conf
DOI :
10.1109/SFCS.1985.61
Filename :
4568127
Link To Document :
بازگشت