Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-032 | 3rd April 2001 00:00

Separation of NP-completeness Notions

RSS-Feed




TR01-032
Authors: A. Pavan, Alan L. Selman
Publication: 27th April 2001 23:09
Downloads: 3237
Keywords: 


Abstract:

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 Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we make no assumptions about stochastic properties of NP.



ISSN 1433-8092 | Imprint