DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2018.40

Nonuniform Reductions and NP-Completeness

Authors: John M. Hitchcock and Hadi Shafei

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP0completeness, obtaining both separations and upper bounds for nonuniform completeness vs uniform complessness in NP. Under various hypotheses, we obtain the following separations: 1. There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice. 2. There is a set complete for NP under nonuniform many-one reductions with polynomial-size advice, but not under uniform Turing reductions. That is, polynomial nonuniformity is stronger than a polynomial number of queries. 3. For any fixed polynomial p(n), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use p(n) advice. That is, giving a uniform reduction a second query makes it more powerful than a nonuniform reduction with fixed polynomial advice. 4. There is a set complete for NP under nonuniform many-one reductions with polynomial ad- vice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy theorem also holds for other reducibilities, such as truth-table and Turing. We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, the same statement for truth-table reductions and truth-table completeness also holds.

Cite as

John M. Hitchcock and Hadi Shafei. Nonuniform Reductions and NP-Completeness. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.STACS.2018.40,
  author =	{Hitchcock, John M. and Shafei, Hadi},
  title =	{{Nonuniform Reductions and NP-Completeness}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.40},
  URN =		{urn:nbn:de:0030-drops-85217},
  doi =		{10.4230/LIPIcs.STACS.2018.40},
  annote =	{Keywords: computational complexity, NP-completeness, reducibility, nonuniform complexity}
}

Document

DOI: 10.4230/LIPIcs.STACS.2016.42

Autoreducibility of NP-Complete Sets

Authors: John M. Hitchcock and Hadi Shafei

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following: - For every k >= 2, there is a k-T-complete set for NP that is k-T autoreducible, but is not k-tt autoreducible or (k-1)-T autoreducible. - For every k >= 3, there is a k-tt-complete set for NP that is k-tt autoreducible, but is not (k-1)-tt autoreducible or (k-2)-T autoreducible. - There is a tt-complete set for NP that is tt-autoreducible, but is not btt-autoreducible. Under the stronger assumption that there is a p-generic set in NP cap coNP, we show: - For every k >= 2, there is a k-tt-complete set for NP that is k-tt autoreducible, but is not (k-1)-T autoreducible. Our proofs are based on constructions from separating NP-completeness notions. For example, the construction of a 2-T-complete set for NP that is not 2-tt-complete also separates 2-T-autoreducibility from 2-tt-autoreducibility.

Cite as

John M. Hitchcock and Hadi Shafei. Autoreducibility of NP-Complete Sets. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 42:1-42:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hitchcock_et_al:LIPIcs.STACS.2016.42,
  author =	{Hitchcock, John M. and Shafei, Hadi},
  title =	{{Autoreducibility of NP-Complete Sets}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{42:1--42:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.42},
  URN =		{urn:nbn:de:0030-drops-57437},
  doi =		{10.4230/LIPIcs.STACS.2016.42},
  annote =	{Keywords: computational complexity, NP-completeness, autoreducibility, genericity}
}

Search Results

Documents authored by Shafei, Hadi

Nonuniform Reductions and NP-Completeness

Abstract

Cite as

Autoreducibility of NP-Complete Sets

Abstract

Cite as

Thanks for your feedback!

Could not send message