Document Open Access Logo

NP-Hardness of Circuit Minimization for Multi-Output Functions

Authors Rahul Ilango, Bruno Loff , Igor C. Oliveira

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.22.pdf
  • Filesize: 0.69 MB
  • 36 pages

Document Identifiers

Author Details

Rahul Ilango
  • Massachusetts Institute of Technology, Cambridge, MA, US
Bruno Loff
  • University of Porto and INESC-Tec, Portugal
Igor C. Oliveira
  • University of Warwick, Coventry, UK

Funding

  • Ilango, Rahul: This work was supported in part by an Akamai Presidential Fellowship.
  • Loff, Bruno: The author was the recipient of FCT postdoctoral grant number SFRH/BPD/116010/2016. This work is financed by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project UIDB/50014/2020.
  • Oliveira, Igor C.: This work was supported in part by a Royal Society University Research Fellowship.

Acknowledgements

Igor C. Oliveira would like to thank Ján Pich and Rahul Santhanam for discussions on the complexity of circuit minimization for partial Boolean functions. Bruno Loff would like to thank Eric Allender for posing a question that inspired some of the results in this work, and the Higher School of Economics for inviting him to the conference "Randomness, Information, Complexity", in honor of Alexander Shen and Nikolay Vereshchagin’s 60th birthday, where said question was asked. Rahul Ilango would like to thank Eric Allender, Marco Carmosino, Russell Impagliazzo, Michael Saks, Rahul Santhanam, and Ryan Williams for their encouragement, suggestions, and helpful discussions.

Cite As Get BibTex

Rahul Ilango, Bruno Loff, and Igor C. Oliveira. NP-Hardness of Circuit Minimization for Multi-Output Functions. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 22:1-22:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.22

Abstract

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an explicitly given function is NP-complete. While this is known to hold in restricted models such as DNFs, making progress with respect to more expressive classes of circuits has been elusive. 
In this work, we establish the first NP-hardness result for circuit minimization of total functions in the setting of general (unrestricted) Boolean circuits. More precisely, we show that computing the minimum circuit size of a given multi-output Boolean function f : {0,1}^n → {0,1}^m is NP-hard under many-one polynomial-time randomized reductions. Our argument builds on a simpler NP-hardness proof for the circuit minimization problem for (single-output) Boolean functions under an extended set of generators.
Complementing these results, we investigate the computational hardness of minimizing communication. We establish that several variants of this problem are NP-hard under deterministic reductions. In particular, unless 𝖯 = 𝖭𝖯, no polynomial-time computable function can approximate the deterministic two-party communication complexity of a partial Boolean function up to a polynomial. This has consequences for the class of structural results that one might hope to show about the communication complexity of partial functions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • MCSP
  • circuit minimization
  • communication complexity
  • Boolean circuit

Metrics

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

Related Versions

References

  1. Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, and Toniann Pitassi. The complexity of properly learning simple concept classes. Journal of Computer and System Sciences, 74(1):16-34, 2008. Google Scholar
  2. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 25-32, 2014. Google Scholar
  3. Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan. Minimum circuit size, graph isomorphism, and related problems. SIAM Journal on Computing, 47(4):1339-1372, 2018. Google Scholar
  4. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks. Minimizing disjunctive normal form formulas and AC⁰ circuits given a truth table. SIAM Journal on Computing, 38(1):63-84, 2008. Google Scholar
  5. Eric Allender and Shuichi Hirahara. New insights on the (non-)hardness of circuit minimization and related problems. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 54:1-54:14, 2017. Google Scholar
  6. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. Computational Complexity, 26(2):469-496, 2017. Google Scholar
  7. Eric Allender, Rahul Ilango, and Neekon Vafa. The non-hardness of approximating circuit size. In International Computer Science Symposium in Russia (CSR), pages 13-24, 2019. Google Scholar
  8. Anurag Anshu, Naresh Goud Boddu, and Dave Touchette. Quantum log-approximate-rank conjecture is also false. arXiv, 2018. URL: http://arxiv.org/abs/1811.10525.
  9. Benny Applebaum, Boaz Barak, and David Xiao. On basing lower-bounds for learning on worst-case assumptions. In Symposium on Foundations of Computer Science (FOCS), pages 211-220, 2008. Google Scholar
  10. Theodore P. Baker, John Gill, and Robert Solovay. Relativizations of the P =? NP question. SIAM Journal on Computing, 4(4):431-442, 1975. Google Scholar
  11. Avrim Blum, Merrick L. Furst, Michael J., and Richard J. Lipton. Cryptographic primitives based on hard learning problems. In International Cryptology Conference (CRYPTO), pages 278-291, 1993. Google Scholar
  12. Avrim L. Blum and Ronald L. Rivest. Training a 3-node neural network is np-complete. Neural Networks, 5(1):117-127, 1992. Google Scholar
  13. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam’s razor. Information Processing Letters, 24(6):377-380, 1987. Google Scholar
  14. Andrej Bogdanov and Luca Trevisan. Average-case complexity. Foundations and Trends in Theoretical Computer Science, 2(1), 2006. Google Scholar
  15. Dan Boneh and Richard J. Lipton. Amplification of weak learning under the uniform distribution. In Conference on Learning Theory (COLT), pages 347-351, 1993. Google Scholar
  16. Joan Boyar, Philip Matthews, and René Peralta. On the shortest linear straight-line program for computing linear forms. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 168-179, 2008. Google Scholar
  17. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Conference on Computational Complexity (CCC), pages 10:1-10:24, 2016. Google Scholar
  18. Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of gap-Hamming-distance. SIAM Journal on Computing, 41(5):1299-1317, 2012. URL: https://doi.org/10.1137/120861072.
  19. Arkadev Chattopadhyay, Nikhil S Mande, and Suhail Sherif. The log-approximate-rank conjecture is false. In Symposium on Theory of Computing (STOC), pages 42-53. ACM, 2019. Google Scholar
  20. Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis. Circuit lower bounds for MCSP from local pseudorandom generators. Electronic Colloquium on Computational Complexity (ECCC), 26:22, 2019. Google Scholar
  21. Gil Cohen and Igor Shinkar. The complexity of DNF of parities. In Innovations in Theoretical Computer Science (ITCS), pages 47-58, 2016. Google Scholar
  22. Sebastian Czort. The complexity of minimizing disjunctive normal form formulas. Master’s Thesis, University of Aarhus, 1999. Google Scholar
  23. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634-652, 1998. Google Scholar
  24. Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57(2):187-199, 1998. Google Scholar
  25. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function. In Symposium on Foundations of Computer Science (FOCS), pages 89-98, 2016. Google Scholar
  26. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  27. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. AC⁰[p] lower bounds against MCSP via the coin problem. Electronic Colloquium on Computational Complexity (ECCC), 26:18, 2019. Google Scholar
  28. Mika Göös and Toniann Pitassi. Communication lower bounds via critical block sensitivity. SIAM Journal on Computing, 47(5):1778-1806, 2018. URL: https://doi.org/10.1137/16M1082007.
  29. Gary D. Hachtel and Fabio Somenzi. Logic synthesis and verification algorithms. Springer, 2006. Google Scholar
  30. Thomas R. Hancock, Tao Jiang, Ming Li, and John Tromp. Lower bounds on learning decision lists and trees. Information and Computation, 126(2):114-122, 1996. Google Scholar
  31. Johan Hastad. Clique is hard to approximate within n^1-ε. In Symposium on Foundations of Computer Science (FOCS), pages 627-636, 1996. Google Scholar
  32. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In Symposium on Foundations of Computer Science (FOCS), pages 247-258, 2018. Google Scholar
  33. Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam. NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. In Computational Complexity Conference (CCC), pages 5:1-5:31, 2018. Google Scholar
  34. Shuichi Hirahara and Rahul Santhanam. On the average-case complexity of MCSP and its variants. In Computational Complexity Conference (CCC), pages 7:1-7:20, 2017. Google Scholar
  35. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In Conference on Computational Complexity (CCC), pages 18:1-18:20, 2016. Google Scholar
  36. John M. Hitchcock and Aduri Pavan. On the NP-completeness of the minimum circuit size problem. In Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pages 236-245, 2015. Google Scholar
  37. Sangxia Huang. Improved hardness of approximating chromatic number. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 233-243, 2013. Google Scholar
  38. Rahul Ilango. AC⁰[p] lower bounds and NP-hardness for variants of MCSP. Electronic Colloquium on Computational Complexity (ECCC), 26:21, 2019. Google Scholar
  39. Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The Power of Natural Properties as Oracles. In Computational Complexity Conference (CCC), volume 102, pages 7:1-7:20, 2018. Google Scholar
  40. Kazuo Iwama and Hiroki Morizumi. An explicit lower bound of 5n - o(n) for boolean circuits. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 353-364, 2002. Google Scholar
  41. J. Stephen Judd. Learning in networks is hard. In International Conference on Neural Networks (ICNN), volume 2, pages 685-692, 1987. Google Scholar
  42. Stasys Jukna. Boolean function complexity: advances and frontiers, volume 27. Springer, 2012. Google Scholar
  43. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Symposium on Theory of Computing (STOC), pages 73-79, 2000. Google Scholar
  44. Maurice Karnaugh. The map method for synthesis of combinational logic circuits. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 72(5):593-599, 1953. Google Scholar
  45. Michael J. Kearns and Leslie G. Valiant. Cryptographic limitations on learning boolean formulae and finite automata. J. ACM, 41(1):67-95, 1994. URL: https://doi.org/10.1145/174644.174647.
  46. Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994. Google Scholar
  47. Subhash Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Symposium on Foundations of Computer Science (FOCS), pages 600-609, 2001. Google Scholar
  48. Subhash Khot and Rishi Saket. Hardness of minimizing and learning DNF expressions. In Symposium on Foundations of Computer Science (FOCS), pages 231-240, 2008. Google Scholar
  49. Ker-I Ko. On the complexity of learning minimum time-bounded Turing machines. SIAM Journal on Computing, 20(5):962-986, 1990. Google Scholar
  50. Pravesh K. Kothari and Roi Livni. Improper learning by refuting. In Innovations in Theoretical Computer Science (ITCS), pages 55:1-55:10, 2018. Google Scholar
  51. Jan Krajícek. Forcing with Random Variables and Proof Complexity. Cambridge University Press, 2011. Google Scholar
  52. Eyal Kushilevitz. Communication complexity. In Advances in Computers, volume 44, pages 331-360. Elsevier, 1997. Google Scholar
  53. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  54. Eyal Kushilevitz and Enav Weinreb. On the complexity of communication complexity. In Symposium on Theory of Computing (STOC), pages 465-474, 2009. Google Scholar
  55. Leonid Levin. Universal sequential search problems. Problemy Peredachi Informatsii, 9(3):115-116, 1973. Google Scholar
  56. László Lovász and Michael Saks. Lattices, mobius functions and communications complexity. In Symposium on Foundations of Computer Science (FOCS), pages 81-90, 1988. Google Scholar
  57. Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960-981, 1994. Google Scholar
  58. William J. Masek. Some NP-complete set covering problems. Unpublished Manuscript, 1979. Google Scholar
  59. Edward J. McCluskey. Introduction to the theory of switching circuits. McGraw-Hill, 1965. Google Scholar
  60. Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In Symposium on Theory of Computing (STOC), 2019. Google Scholar
  61. Moritz Müller and Ján Pich. Feasibly constructive proofs of succinct weak circuit lower bounds. Electronic Colloquium on Computational Complexity (ECCC), 24:144, 2017. Google Scholar
  62. Cody D. Murray and Richard Ryan Williams. On the (non) NP-hardness of computing circuit complexity. In Conference on Computational Complexity (CCC), pages 365-380, 2015. Google Scholar
  63. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. In Conference on Computational Complexity (CCC), 2019. Google Scholar
  64. Igor Carboni Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1-18:49, 2017. Google Scholar
  65. Igor Carboni Oliveira and Rahul Santhanam. Hardness magnification for natural problems. In Symposium on Foundations of Computer Science (FOCS), pages 65-76, 2018. Google Scholar
  66. James Orlin. Contentment in graph theory: covering graphs with cliques. Indagationes Mathematicae, 80(5):406-424, 1977. Google Scholar
  67. Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the ACM, 35(4):965-984, 1988. Google Scholar
  68. Pavel Pudlák, Vojtech Rödl, and Petr Savický. Graph complexity. Acta Informatica, 25(5):515-535, 1988. Google Scholar
  69. Netanel Raviv. Truth table minimization of computational models. CoRR/arXiv, abs/1306.3766, 2013. URL: http://arxiv.org/abs/1306.3766.
  70. Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. Google Scholar
  71. Ronald L. Rivest. Learning decision lists. Machine Learning, 2(3):229-246, 1987. Google Scholar
  72. J. Paul Roth and Richard M. Karp. Minimization over boolean graphs. IBM Journal of Research and Development, 6(2):227-238, 1962. Google Scholar
  73. Christoph Scholl. Functional decomposition with applications to FPGA synthesis. Kluwer Academic Publishers, 2001. Google Scholar
  74. Makrand Sinha and Ronald de Wolf. Exponential separation between quantum communication and logarithm of approximate rank. arXiv, 2018. URL: http://arxiv.org/abs/1811.10090.
  75. Boris A Trakhtenbrot. A survey of Russian approaches to perebor (brute-force search) algorithms. Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
  76. Luca Trevisan. Non-approximability results for optimization problems on bounded degree instances. In Symposium on Theory of Computing (STOC), pages 453-461, 2001. Google Scholar
  77. Christopher Umans, Tiziano Villa, and Alberto L. Sangiovanni-Vincentelli. Complexity of two-level logic minimization. IEEE Trans. on CAD of Integrated Circuits and Systems, 25(7):1230-1246, 2006. Google Scholar
  78. Salil P. Vadhan. On learning vs. refutation. In Conference on Learning Theory (COLT), pages 1835-1848, 2017. Google Scholar
  79. Marcin Wrochna and Stanislav Živnỳ. Improved hardness for H-colourings of G-colourable graphs. arXiv, 2019. URL: http://arxiv.org/abs/1907.00872.
  80. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing (preliminary report). In Symposium on Theory of Computing (STOC), pages 209-213, 1979. URL: https://doi.org/10.1145/800135.804414.
  81. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In Symposium on Foundations of Computer Science (FOCS), pages 80-91, 1982. Google Scholar
  82. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Symposium on Theory of Computing (STOC), pages 681-690, 2006. 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