Separation of NP-completeness notions

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 01 Jan 2001Publisher:IEEE Comput. SocJournal:Proceedings 16th Annual IEEE Conference on Computational Complexity

Authors: Aduri Pavan; Alan L. Selman;

doi: 10.1109/ccc.2001.933875 , 10.1137/s0097539701387039

Separation of NP-completeness notions

- Summary
- Subjects
- Metrics

Abstract

Summary: 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 \({\leq}^P_T\)-complete but not \({\leq}^P_{tt}\)-complete. We provide fairly thorough analyses of the hypotheses that we introduce.

Related Organizations

State University of New York at Potsdam
United States
University at Buffalo, State University of New York
United States
State University of New York
United States

Keywords

\(p\)-selectivity, truth-table completeness, Complexity classes (hierarchies, relations among complexity classes, etc.), Turing completeness, many-one completeness, \(p\)-genericity

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	15
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%