Abstract
We show that every read-once nondeterministic branching program computing the Minimum Circuit Size Problem on inputs of length N has size \(\varOmega (N^{\log \log (N)})\). This is the first superpolynomial lower bound on the size of computing \({\textsc {MCSP} }\). This lower bound is tight for the version of \({\textsc {MCSP} }\) restricted to a linear circuit size parameter.
To show this result we adapt a conditional lower bound of Ilango [10] on the deterministic Turing Machine time complexity of computing \({\textsc {MCSP} }^{*}\), the generalization of \({\textsc {MCSP} }\) to partial functions. In contrast, our lower bound is unconditional and holds even for the total \({\textsc {MCSP} }\) function.
En route, we get two results that may be of independent interest:
-
The size of the minimal computing \({\textsc {MCSP} }\) equals, up to a constant factor, the size of the minimal computing \({\textsc {MCSP} }^{*}\);
-
The size of any computing \((2n \times 2n)\)-Bipartite Independent Set is \(\varOmega (n!)\).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Sometimes are also called decision diagrams.
- 2.
See Lemma 14 in [4].
- 3.
OBDD is a in which variables in every path from the source to a sink appear in the same order.
- 4.
We will instantiate this definition for \(D = \{0,1\}\) and \(D = \{0,1,*\}\).
- 5.
We ignore all the edges except for ones between the sets \([n] \times [n]\) and \(\{n+1,\dots 2n\} \times \{n+1,\dots ,2n\}\), the second argument is represented in binary form.
- 6.
Notice that here * is a value of a variable and does not indicate that a variable is unassigned.
References
Borodin, A., Razborov, A.A., Smolensky, R.: On lower bounds for read-K-times branching programs. Comput. Complex. 3, 1–18 (1993)
Chen, L., Jin, C., Ryan Williams, R.: Hardness magnification for all sparse NP languages. In: FOCS 2019, pp. 1240–1255. IEEE Computer Society (2019)
Cheraghchi, M., Hirahara, S., Myrisiotis, D., Yoshida, Y.: One-tape turing machine and branching program lower bounds for MCSP. In: Bläser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), vol. 187, pp. 23:1–23:19. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl (2021). ISBN 978-3-95977-180-1. https://doi.org/10.4230/LIPIcs.ICALP.2019.39. https://drops.dagstuhl.de/opus/volltexte/2021/13668
Cheraghchi, M., Kabanets, V., Lu, Z., Myrisiotis, D.: Circuit lower bounds for MCSP from local pseudorandom generators. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, July 2019, vol. 132, pp. 9–12 (2019). LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 39(1–39), 14 (2019). https://doi.org/10.4230/LIPIcs.STACS.2021.23
Cobham, A.: The recognition problem for the set of perfect squares. In: 7th Annual Symposium on Switching and Automata Theory (SWAT 1966), pp. 78–87. https://doi.org/10.1109/SWAT.1966.30
Find, M.G., Golovnev, A., Hirsch, E.A., Kulikov, A.S.: A better-than-3n lower bound for the circuit complexity of an explicit function. In: FOCS 2016, pp. 89–98. IEEE Computer Society (2016)
Forbes, M.A., Kelley, Z.: Pseudorandom generators for readonce branching programs, in any order. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 946–955. IEEE (2018)
Glinskih, L., Itsykson, D.: Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs. In: Larsen, K.G., Bodlaender, H.L., Raskin, J.-F. (eds.) 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), vol. 83. Leibniz International Proceedings in Informatics (LIPIcs) (2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl 26(1–26), 12 (2017). ISBN 978-3-95977-046-0. https://doi.org/10.4230/LIPIcs.MFCS.2017.26. https://drops.dagstuhl.de/opus/volltexte/2017/8076
Golovnev, A., Ilango, R., Impagliazzo, R., Kabanets, V., Kolokolova, A., Tal, A.: AC0[p] lower bounds against MCSP via the coin problem. In: ICALP, vol. 132, pp. 66:1–66:15. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
Ilango, R.: Constant depth formula and partial function versions of MCSP are hard. In: FOCS 2020, pp. 424–433. IEEE (2020)
Ilango, R., Ren, H., Santhanam, R.: Hardness on any samplable distribution suffices: new characterizations of one-way functions by meta-complexity. In: Electronic Colloquium on Computational Complexity, p. 82 (2021)
Kabanets, V., Cai, J.: Circuit minimization problem. In: STOC, pp. 73–79. ACM (2000)
Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. SIAM J. Comput. 47(3), 675–702 (2018)
Lukas, S., Czort, S.L.A.: The complexity of minimizing disjunctive normal form formulas (1999)
McKay, D.M., Murray, C.D., Ryan Williams, R.: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 1215–1225. Association for Computing Machinery, Phoenix (2019). ISBN 9781450367059
Murray, C.D., Ryan Williams, R.: On the (non) NP-hardness of computing circuit complexity. Theory Comput. 13(4), 1–22 (2017)
Pratt, V.R.: The effect of basis on size of boolean expressions. In: FOCS, pp. 119–121. IEEE Computer Society (1975)
Santhanam, R.: Pseudorandomness and the minimum circuit size problem. In: ITCS, vol. 151, pp. 68:1–68:26. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
Sieling, D.: The complexity of minimizing and learning OBDDs and FBDDs. Discret. Appl. Math. 122(1), 263–282 (2002). ISSN 0166-218X. https://doi.org/10.1016/S0166-218X(01)00324-9. https://www.sciencedirect.com/science/article/pii/S0166218X01003249
Smolensky, R.: On representations by low-degree polynomials. In: Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pp. 130–138 (1993). https://doi.org/10.1109/SFCS.1993.366874
Acknowledgements
We thank Mark Bun, Marco Carmosino, and the anonymous reviewers for their helpful comments and suggestions.
Ludmila Glinskih was supported by NSF grants CCF-1947889 and CCF-1909612. Artur Riazanov received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No. 802020-ERC-HARMONIC.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Glinskih, L., Riazanov, A. (2022). MCSP is Hard for Read-Once Nondeterministic Branching Programs. In: Castañeda, A., Rodríguez-Henríquez, F. (eds) LATIN 2022: Theoretical Informatics. LATIN 2022. Lecture Notes in Computer Science, vol 13568. Springer, Cham. https://doi.org/10.1007/978-3-031-20624-5_38
Download citation
DOI: https://doi.org/10.1007/978-3-031-20624-5_38
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20623-8
Online ISBN: 978-3-031-20624-5
eBook Packages: Computer ScienceComputer Science (R0)