Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deal with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) within a factor of n1 o(1) is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function. Our technique is quite general; we use it also to show that approximating the size of the largest clique in a graph within a factor of n1 o(1) is also NP-intermediate unless NP P/poly. We also prove that MKTP is hard for the complexity class DET under non-uniform NC0 reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of “local” reductions such as NC0m. We exploit this local reduction to obtain several new consequences: — MKTP is not in AC0[p]. — Circuit size lower bounds are equivalent to hardness of a relativized version MKTPA of MKTP under a class of uniform AC0 reductions, for a significant class of sets A. — Hardness of MCSPA implies hardness of MCSPA for a significant class of sets A. This is the first result directly relating the complexity of MCSPA and MCSPA, for any A. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems

Download PDF
27 pages

Loading next page...
 
/lp/association-for-computing-machinery/new-insights-on-the-non-hardness-of-circuit-minimization-and-related-jc0CWhydtQ
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3349616
Publisher site
See Article on Publisher Site

Abstract

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deal with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) within a factor of n1 o(1) is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function. Our technique is quite general; we use it also to show that approximating the size of the largest clique in a graph within a factor of n1 o(1) is also NP-intermediate unless NP P/poly. We also prove that MKTP is hard for the complexity class DET under non-uniform NC0 reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of “local” reductions such as NC0m. We exploit this local reduction to obtain several new consequences: — MKTP is not in AC0[p]. — Circuit size lower bounds are equivalent to hardness of a relativized version MKTPA of MKTP under a class of uniform AC0 reductions, for a significant class of sets A. — Hardness of MCSPA implies hardness of MCSPA for a significant class of sets A. This is the first result directly relating the complexity of MCSPA and MCSPA, for any A.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Sep 12, 2019

Keywords: Computational complexity

References

  • The isomorphism conjecture for constant depth reductions
    Agrawal, Manindra
  • Reductions in circuit complexity: An isomorphism theorem and a gap theorem
    Agrawal, Manindra; Allender, Eric; Rudich, Steven
  • The permanent requires large uniform threshold circuits
    Allender, Eric
  • Arithmetic circuits and counting complexity classes
    Allender, Eric
  • Power from random strings
    Allender, Eric; Buhrman, Harry; Koucký, Michal; van Melkebeek, Dieter; Ronneburger, Detlef
  • Zero knowledge and circuit minimization
    Allender, Eric; Das, Bireswar
  • Minimum circuit size, graph isomorphism and related problems
    Allender, Eric; Grochow, Joshua; van Melkebeek, Dieter; Morgan, Andrew; Moore, Cristopher
  • The minimum oracle circuit size problem
    Allender, Eric; Holden, Dhiraj; Kabanets, Valentine
  • Amplifying lower bounds by means of self-reducibility
    Allender, Eric; Koucký, Michal
  • The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
    Allender, Eric; Koucký, Michal; Ronneburger, Detlef; Roy, Sambuddha
  • Time-space tradeoffs in the counting hierarchy
    Allender, Eric; Koucký, Michal; Ronneburger, Detlef; Roy, Sambuddha; Vinay, V.
  • Relationships among PL, #L, and the determinant
    Allender, Eric; Ogihara, Mitsunori
  • On uniformity within NC 1
    Barrington, D. A. M.; Immerman, N.; Straubing, H.
  • On beating the hybrid argument
    Fefferman, Bill; Shaltiel, Ronen; Umans, Christopher; Viola, Emanuele
  • On promise problems: A survey
    Goldreich, Oded
  • How to construct random functions
    Goldreich, Oded; Goldwasser, Shafi; Micali, Silvio
  • Fast parallel generation of random permutations
    Hagerup, Torben
  • Computational Limitations for Small Depth Circuits
    Håstad, Johan
  • Clique is hard to approximate within n1-ε
    Håstad, Johan
  • A pseudorandom generator from any one-way function
    Håstad, Johan; Impagliazzo, Russell; Levin, Leonid; Luby, Michael
  • On the average-case complexity of MCSP and its variants
    Hirahara, Shuichi; Santhanam, Rahul
  • Limits of minimum circuit size problem as oracle
    Hirahara, Shuichi; Watanabe, Osamu
  • On the NP-completeness of the minimum circuit size problem
    Hitchcock, John M.; Pavan, Aduri
  • The power of natural properties as oracles
    Impagliazzo, R.; Kabanets, V.; Volkovich, I.
  • In search of an easy witness: Exponential time vs
    Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi
  • One-way functions are essential for complexity based cryptography (extended abstract)
    Impagliazzo, Russell; Luby, Michael
  • P = BPP if E requires exponential circuits: Derandomizing the XOR Lemma
    Impagliazzo, Russell; Wigderson, Avi
  • Circuit minimization problem
    Kabanets, Valentine; Cai, Jin-Yi
  • Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
    Klivans, Adam; van Melkebeek, Dieter
  • On the structure of polynomial time reducibility
    Ladner, Richard E.
  • Relativization of questions about log space computability
    Ladner, Richard E.; Lynch, Nancy A.
  • On the (non) NP-hardness of computing circuit complexity
    Murray, Cody; Williams, Ryan
  • Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
    Oliveira, Igor; Santhanam, Rahul
  • One-way functions, hard on average problems, and statistical zero-knowledge proofs
    Ostrovsky, Rafail
  • One-way functions are essential for non-trivial zero-knowledge
    Ostrovsky, Rafail; Wigderson, Avi
  • Natural proofs
    Razborov, Alexander; Rudich, Steven
  • Lower bounds on the size of bounded depth networks over a complete basis with logical addition
    Razborov, Alexander A.
  • Discrete logarithm and minimum circuit size
    Rudow, Michael
  • Algebraic methods in the theory of lower bounds for Boolean circuit complexity
    Smolensky, Roman
  • On the approximability of clique and related maximization problems
    Srinivasan, Aravind
  • Complexity classes defined by counting quantifiers
    Torán, Jacobo
  • On the hardness of graph isomorphism
    Torán, Jacobo
  • An unconditional study of computational zero knowledge
    Vadhan, Salil P.
  • The complexity of constructing pseudorandom generators from hard functions
    Viola, Emanuele
  • Introduction to Circuit Complexity: A Uniform Approach
    Vollmer, Heribert