Separation of NP-completeness notions

被引：0
作者：
Pavan, A [1 ]
Selman, AL [1 ]
机构：
[1] SUNY Buffalo, Dept Comp Sci & Engn, Buffalo, NY 14260 USA
来源：
16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2000年
关键词：
D O I：
10.1109/CCC.2001.933875
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We use hypotheses of structural complexity theory to separate various NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is less than or equal to(T)(P)-complete but not less than or equal to(tt)(P)-complete. We provide fairly thorough analyses of the hypotheses that we introduce.
引用
收藏
页码：78 / 89
页数：12
相关论文
共 32 条
[1]   P-PRINTABLE SETS [J].
ALLENDER, EW ;
RUBINSTEIN, RS .
SIAM JOURNAL ON COMPUTING, 1988, 17 (06) :1193-1202
[2]   508 Separating NP-completeness notions under strong hypotheses [J].
Ambos-Spies, K ;
Bentzien, L .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000, 61 (03) :335-361
[3]   Resource bounded randomness and weakly complete problems [J].
AmbosSpies, K ;
Terwijn, SA ;
Zheng, XZ .
THEORETICAL COMPUTER SCIENCE, 1997, 172 (1-2) :195-207
[4]   DIAGONALIZATIONS OVER POLYNOMIAL-TIME COMPUTABLE SETS [J].
AMBOSSPIES, K ;
FLEISCHHACK, H ;
HUWIG, H .
THEORETICAL COMPUTER SCIENCE, 1987, 51 (1-2) :177-204
[5]   Genericity and measure for exponential time [J].
AmbosSpies, K ;
Neis, HC ;
Terwijn, SA .
THEORETICAL COMPUTER SCIENCE, 1996, 168 (01) :3-19
[6]  
Baker T., 1975, SIAM Journal on Computing, V4, P431, DOI 10.1137/0204037
[7]   BI-IMMUNE SETS FOR COMPLEXITY CLASSES [J].
BALCAZAR, JL ;
SCHONING, U .
MATHEMATICAL SYSTEMS THEORY, 1985, 18 (01) :1-10
[8]   THE POLYNOMIAL-TIME HIERARCHY AND SPARSE ORACLES [J].
BALCAZAR, JL ;
BOOK, RV ;
SCHONING, U .
JOURNAL OF THE ACM, 1986, 33 (03) :603-617
[9]   COMPLETENESS FOR NONDETERMINISTIC COMPLEXITY CLASSES [J].
BUHRMAN, H ;
HOMER, S ;
TORENVLIET, L .
MATHEMATICAL SYSTEMS THEORY, 1991, 24 (03) :179-200
[10]   Inverting onto functions [J].
Fenner, SA ;
Fortnow, L ;
Naik, AV ;
Rogers, JD .
ELEVENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 1996, :213-222
1234