Document Open Access Logo

Does Looking Inside a Circuit Help?

Authors Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.1.pdf
  • Filesize: 494 kB
  • 13 pages

Document Identifiers

Author Details

Russell Impagliazzo
Valentine Kabanets
Antonina Kolokolova
Pierre McKenzie
Shadab Romani

Cite As Get BibTex

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani. Does Looking Inside a Circuit Help?. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.1

Abstract

The Black-Box Hypothesisstates that any property of Boolean functions decided efficiently (e.g., in BPP)  with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an upper bound on its circuit size. If this hypothesis is true, then P neq NP. We focus on the consequences of the hypothesis being false, showing that (under general conditions on the structure of a counterexample) it implies a non-trivial algorithm for CSAT. More specifically, we show that if there is a property F of boolean functions such that F has high sensitivity on some input function f of subexponential circuit complexity (which is a sufficient condition for F being a counterexample to the Black-Box Hypothesis), then CSAT  is solvable by a subexponential-size circuit family. Moreover, if such a counterexample F is symmetric, then CSAT is in Ppoly. These results provide some evidence towards the conjecture (made in this paper) that the Black-Box Hypothesis is false if and only if CSAT is easy.

Subject Classification

Keywords
  • Black-Box Hypothesis
  • Rice's theorem
  • circuit complexity
  • SAT
  • sensitivity of boolean functions
  • decision tree complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Leonard Adleman. Two theorems on random polynomial time. In Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science, pages 75-83, 1978. Google Scholar
  2. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. Computational Complexity, 26(2):469-496, 2017. URL: http://dx.doi.org/10.1007/s00037-016-0124-0.
  3. Andris Ambainis and Jevgēnijs Vihrovs. Size of sets with small sensitivity: A generalization of Simon’s lemma. In International Conference on Theory and Applications of Models of Computation, pages 122-133. Springer International Publishing, 2015. Google Scholar
  4. Laci Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307-318, 1993. Google Scholar
  5. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (im) possibility of obfuscating programs. Journal of the ACM (JACM), 59(2):6, 2012. Google Scholar
  6. Bernd Borchert and Frank Stephan. Looking for an analogue of Rice’s theorem in circuit complexity theory. Math. Log. Q., 46(4):489-504, 2000. URL: http://dx.doi.org/10.1002/1521-3870(200010)46:4<489::AID-MALQ489>3.0.CO;2-F.
  7. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21–43, Oct 2002. Google Scholar
  8. Ashok K Chandra, Larry Stockmeyer, and Uzi Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13(2):423-439, 1984. Google Scholar
  9. Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. Variations on the sensitivity conjecture. Theory of Computing, Graduate Surveys, 2:1-27, 2011. Google Scholar
  10. Lane A. Hemaspaandra and Jörg Rothe. A second step towards complexity-theoretic analogs of Rice’s theorem. Theor. Comput. Sci., 244(1-2):205-217, 2000. Google Scholar
  11. Lane A. Hemaspaandra and Mayur Thakur. Lower bounds and the hardness of counting properties. Theor. Comput. Sci., 326(1-3):1-28, 2004. Google Scholar
  12. Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, and Shadab Romani. Does looking inside a circuit help? Electronic Colloquium on Computational Complexity, 17(109), 2017. Google Scholar
  13. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  14. Russell Impagliazzo and Avi Wigderson. P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 220-229, 1997. Google Scholar
  15. Noam Nisan. CREW PRAMs and decision trees. SIAM Journal on Computing, 20(6):999-1007, 1991. Google Scholar
  16. Noam Nisan and Avi Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49:149-167, 1994. Google Scholar
  17. Ramamohan Paturi and Pavel Pudlák. On the complexity of circuit satisfiability. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 241-250, 2010. Google Scholar
  18. Hans-Ulrich Simon. A tight ω (loglog n)-bound on the time for parallel RAM’s to compute nondegenerated boolean functions. In Foundations of Computation Theory, pages 439-444. Springer, 1983. Google Scholar
  19. Leslie Valiant and Vijay Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85-93, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact