Document Open Access Logo

Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas

Author Rahul Ilango

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.31.pdf
  • Filesize: 0.65 MB
  • 35 pages

Document Identifiers

Author Details

Rahul Ilango
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

During this work the author was supported by an Akamai Presdential fellowship.

Acknowledgements

I want to thank Eric Allender, Mathew Katzman, Aditya Potukuchi, Michael Saks, Rahul Santhanam, and Ryan Williams for many helpful discussions regarding this work.

Cite AsGet BibTex

Rahul Ilango. Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 31:1-31:35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.31

Abstract

A longstanding open question is whether there is an equivalence between the computational task of determining the minimum size of any circuit computing a given function and the task of producing a minimum-sized circuit for a given function. While it is widely conjectured that both tasks require "perebor," or brute-force search, researchers have not yet ruled out the possibility that the search problem requires exponential time but the decision problem has a linear time algorithm. In this paper, we make progress in connecting the search and decision complexity of minimizing formulas. Let MFSP denote the problem that takes as input the truth table of a Boolean function f and an integer size parameter s and decides whether there is a formula for f of size at most s. Let Search- denote the corresponding search problem where one has to output some optimal formula for computing f. Our main result is that given an oracle to MFSP, one can solve Search-MFSP in time polynomial in the length N of the truth table of f and the number t of "near-optimal" formulas for f, in particular O(N⁶t²)-time. While the quantity t is not well understood, we use this result (and some extensions) to prove that given an oracle to MFSP: - there is a deterministic 2^O(N/(log log N))-time oracle algorithm for solving Search-MFSP on all but a o(1)-fraction of instances, and - there is a randomized O(2^.67N)-time oracle algorithm for solving Search-MFSP on all instances. Intriguingly, the main idea behind our algorithms is in some sense a "reverse application" of the gate elimination technique.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Problems, reductions and completeness
Keywords
  • minimum circuit size problem
  • minimum formula size problem
  • gate elimination
  • search to decision reduction
  • self-reducibility

Metrics

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

References

  1. Eric Allender. The new complexity landscape around circuit minimization. In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, and Claudio Zandron, editors, Language and Automata Theory and Applications - 14th International Conference, LATA 2020, Milan, Italy, March 4-6, 2020, Proceedings, volume 12038 of Lecture Notes in Computer Science, pages 3-16. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-40608-0_1.
  2. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467-1493, 2006. Google Scholar
  3. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. Inf. Comput., 256:2-8, 2017. Google Scholar
  4. Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded kolmogorov complexity in computational complexity theory. Journal of Computer and System Sciences, 77(1):14-40, 2011. Google Scholar
  5. David Buchfuhrer and Christopher Umans. The complexity of boolean formula minimization. J. Comput. Syst. Sci., 77(1):142-153, 2011. Google Scholar
  6. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Proceedings of the 31st Conference on Computational Complexity, 2016. Google Scholar
  7. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. Ac^0[p] lower bounds against MCSP via the coin problem. In ICALP, volume 132 of LIPICS, pages 66:1-66:15, 2019. Google Scholar
  8. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 247-258, 2018. Google Scholar
  9. Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam. NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. In 33rd Computational Complexity Conference, CCC, volume 102, pages 5:1-5:31, 2018. Google Scholar
  10. Valentine Kabanets and Jin-Yi Cai. Circuit minimization problem. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC ’00, page 73–79, 2000. Google Scholar
  11. S. A. Lozhkin. Tighter bounds on the complexity of control systems from some classes. Mat. Voprosy Kibernetiki 6, pages 189-214 (in Russian), 1996. Google Scholar
  12. Oleg B. Lupanov. Complexity of formula realization of functions of logical algebra. Problemy Kibernetiki, 3:61-80, 1960. Google Scholar
  13. William J. Masek. Some NP-complete set covering problems. Unpublished Manuscript, 1979. Google Scholar
  14. Cody D. Murray and R. Ryan Williams. On the (non) np-hardness of computing circuit complexity. Theory of Computing, 13(1):1-22, 2017. Google Scholar
  15. Erkki Mäkinen. Generating random binary trees — a survey. Information Sciences, 115(1):123-136, 1999. Google Scholar
  16. Nicholas Pippenger. Information theory and the complexity of boolean functions. Mathematical Systems Theory, 10:129-167, January 1977. Google Scholar
  17. Alexander A. Razborov and Steven Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. Google Scholar
  18. Michael Rudow. Discrete logarithm and minimum circuit size. Inf. Process. Lett., 128:1-4, 2017. Google Scholar
  19. Rahul Santhanam. Pseudorandomness and the minimum circuit size problem. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of LIPIcs, pages 68:1-68:26, 2020. Google Scholar
  20. B. A. Trakhtenbrot. A survey of russian approaches to perebor (brute-force searches) algorithms. IEEE Ann. Hist. Comput., 6(4):384–400, October 1984. 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 Imprint Privacy Contact