Gu, Xiaoyang ;
Hitchcock, John M. ;
Pavan, Aduri
Collapsing and Separating Completeness Notions under AverageCase and WorstCase Hypotheses
Abstract
This paper presents the following results on sets that are complete for $\NP$.
\begin{enumerate}
\item If there is a problem in $\NP$ that requires $\twonO$ time at almost all lengths, then every manyone NPcomplete set is complete under lengthincreasing reductions that are computed by polynomialsize circuits.
\item If there is a problem in $\CoNP$ that cannot be solved by polynomialsize nondeterministic circuits, then every manyone complete set is complete under lengthincreasing reductions that are computed by polynomialsize circuits.
\item If there exist a oneway permutation that is secure against subexponentialsize circuits and there is a hard tally language in $\NP \cap \CoNP$, then there is a Turing complete language for $\NP$
that is not manyone complete.
\end{enumerate}
Our first two results use worstcase hardness hypotheses whereas
earlier work that showed similar results relied on averagecase or
almosteverywhere hardness assumptions. The use of averagecase and
worstcase hypotheses in the last result is unique as previous results
obtaining the same consequence relied on almosteverywhere hardness
results.
BibTeX  Entry
@InProceedings{gu_et_al:LIPIcs:2010:2462,
author = {Xiaoyang Gu and John M. Hitchcock and Aduri Pavan},
title = {{Collapsing and Separating Completeness Notions under AverageCase and WorstCase Hypotheses}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {429440},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2462},
URN = {urn:nbn:de:0030drops24627},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2462},
annote = {Keywords: Computational complexity, NPcompleteness}
}
2010
Keywords: 

Computational complexity, NPcompleteness 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Related Scholarly Article: 


Issue date: 

2010 
Date of publication: 

2010 