The non-hardness of approximating circuit size

Eric Allender, Rahul Ilango, Neekon Vafa

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

7 Scopus citations

Abstract

The Minimum Circuit Size Problem (MCSP ) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions [4], and is provably not hard under “local” reductions computable in TIME(n0.49) [22]. The question of whether MCSP is NP -hard (or indeed, hard even for small subclasses of P ) under some of the more familiar notions of reducibility (such as many-one or Turing reductions computable in polynomial time or in AC0 ) is closely related to many of the longstanding open questions in complexity theory [7, 8, 16–18, 20, 22]. All prior hardness results for MCSP hold also for computing somewhat weak approximations to the circuit complexity of a function [3, 4, 9, 16, 21, 27]. (Subsequent to our work, a new hardness result has been announced [19] that relies on more exact size computations.) Some of these results were proved by exploiting a connection to a notion of time-bounded Kolmogorov complexity (KT ) and the corresponding decision problem (MKTP ). More recently, a new approach for proving improved hardness results for MKTP was developed [5, 7], but this approach establishes only hardness of extremely good approximations of the form 1 + o(1 ), and these improved hardness results are not yet known to hold for MCSP. In particular, it is known that MKTP is hard for the complexity class DET under nonuniform (formula presented) reductions, implying MKTP is not in AC0[ p] for any prime p [7]. It was still open if similar circuit lower bounds hold for MCSP. (But see [13, 19].) One possible avenue for proving a similar hardness result for MCSP would be to improve the hardness of approximation for MKTP beyond 1 + o(1 ) to ω(1 ), as KT -complexity and circuit size are polynomially-related. In this paper, we show that this approach cannot succeed. More specifically, we prove that PARITY does not reduce to the problem of computing superlinear approximations to KT -complexity or circuit size via AC0 -Turing reductions that make O(1) queries. This is significant, since approximating any set in P/ poly AC0 -reduces to just one query of a much worse approximation of circuit size or KT -complexity [24]. For weaker approximations, we also prove non-hardness under more powerful reductions. Our non-hardness results are unconditional, in contrast to conditional results presented in [7] (for more powerful reductions, but for much worse approximations). This highlights obstacles that would have to be overcome by any proof that MKTP or MCSP is hard for NP under AC0 reductions. It may also be a step toward confirming a conjecture of Murray and Williams, that MCSP is not NP -complete under logtime-uniform (formula presented) reductions [22].

Original languageEnglish (US)
Title of host publicationComputer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings
EditorsRené van Bevern, Gregory Kucherov
PublisherSpringer Verlag
Pages13-24
Number of pages12
ISBN (Print)9783030199548
DOIs
StatePublished - 2019
Event14th International Computer Science Symposium in Russia, CSR 2019 - Novosibirsk, Russian Federation
Duration: Jul 1 2019Jul 5 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11532 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Computer Science Symposium in Russia, CSR 2019
Country/TerritoryRussian Federation
CityNovosibirsk
Period7/1/197/5/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Minimum Circuit Size Problem
  • NP-completeness
  • Reductions
  • Time-bounded Kolmogorov complexity

Fingerprint

Dive into the research topics of 'The non-hardness of approximating circuit size'. Together they form a unique fingerprint.

Cite this