Circuit lower bounds from NP-hardness of MCSP under turing reductions

Michael Saks, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

The fundamental Minimum Circuit Size Problem is a well-known example of a problem that is neither known to be in P nor known to be NP-hard. Kabanets and Cai [18] showed that if MCSP is NP-hard under “natural” m-reductions, superpolynomial circuit lower bounds for exponential time would follow. This has triggered a long line of work on understanding the power of reductions to MCSP. Nothing was known so far about consequences of NP-hardness of MCSP under general Turing reductions. In this work, we consider two structured kinds of Turing reductions: parametric honest reductions and natural reductions. The latter generalize the natural reductions of Kabanets and Cai to the case of Turing-reductions. We show that NP-hardness of MCSP under these kinds of Turing-reductions imply superpolynomial circuit lower bounds for exponential time.

Original languageEnglish (US)
Title of host publication35th Computational Complexity Conference, CCC 2020
EditorsShubhangi Saraf
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771566
DOIs
StatePublished - Jul 1 2020
Event35th Computational Complexity Conference, CCC 2020 - Virtual, Online, Germany
Duration: Jul 28 2020Jul 31 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume169
ISSN (Print)1868-8969

Conference

Conference35th Computational Complexity Conference, CCC 2020
Country/TerritoryGermany
CityVirtual, Online
Period7/28/207/31/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Circuit lower bounds
  • Minimum Circuit Size Problem
  • Turing reductions

Fingerprint

Dive into the research topics of 'Circuit lower bounds from NP-hardness of MCSP under turing reductions'. Together they form a unique fingerprint.

Cite this