2026-07-22T21:50:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2462 2024-03-06T10:33:24Z ddc:004 open_access

Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses Gu, Xiaoyang Hitchcock, John M. Pavan, Aduri Computational complexity NP-completeness 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 many-one NP-complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. \item If there is a problem in $\CoNP$ that cannot be solved by polynomial-size nondeterministic circuits, then every many-one complete set is complete under length-increasing reductions that are computed by polynomial-size circuits. \item If there exist a one-way permutation that is secure against subexponential-size circuits and there is a hard tally language in $\NP \cap \CoNP$, then there is a Turing complete language for $\NP$ that is not many-one complete. \end{enumerate} Our first two results use worst-case hardness hypotheses whereas earlier work that showed similar results relied on average-case or almost-everywhere hardness assumptions. The use of average-case and worst-case hypotheses in the last result is unique as previous results obtaining the same consequence relied on almost-everywhere hardness results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiaoyang Gu and John M. Hitchcock and Aduri Pavan 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2462 urn:nbn:de:0030-drops-24627 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2462 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode