Going Meta on the Minimum Circuit Size Problem: How Hard Is It to Show How Hard Showing Hardness Is?
Researcher ORCID Identifier
https://orcid.org/0000-0002-4789-6786
Graduation Year
2021
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Nicholas Pippenger
Reader 2
Ran Libeskind-Hadas
Terms of Use & License Information
Rights Information
2021 Zoë Ruha Bell
Abstract
The Minimum Circuit Size Problem (MCSP) is a problem with a long history in computational complexity theory which has recently experienced a resurgence in attention. MCSP takes as input the description of a Boolean function f as a truth table as well as a size parameter s, and outputs whether there is a circuit that computes f of size ≤ s. It is of great interest whether MCSP is NP-complete, but there have been shown to be many technical obstacles to proving that it is. Most of these results come in the following form: If MCSP is NP-complete under a certain type of reduction, then we get a breakthrough in complexity theory that seems well beyond current techniques. These results indicate that it is unlikely we will be able to show MCSP is NP-complete under these kinds of reductions anytime soon.
I seek to add to this line of work, in particular focusing on an approximation version of MCSP which is central to some of its connections to other areas of complexity theory, as well as some other variants on the problem. Let f indicate an n-ary Boolean function that thus has a truth table of size 2n. I have used the approach of Saks and Santhanam (2020) to prove that if on input f approximating MCSP within a factor superpolynomial in n is NP-complete under general polynomial-time Turing reductions, then E ⊈ P/poly (a dramatic circuit lower bound). This provides a barrier to Hirahara (2018)'s suggested program of using the NP-completeness of a 2(1-𝜖)n-approximation version of MCSP to show that if NP is hard in the worst case (P ≠ NP), it is also hard on average (i.e., to rule out Heuristica). However, using randomized reductions to do so remains potentially tractable.
I also extend the results of Saks and Santhanam (2020) to what I define as Σk-MCSP and Q-MCSP, getting stronger circuit lower bounds, namely E ⊈ ΣkP/poly and E ⊈ PH/poly, just from their NP-hardness. Since Σk-MCSP and Q-MCSP seem to be harder problems than MCSP, at first glance one might think it would be easier to show that Σk-MCSP or Q-MCSP is NP-hard, but my results demonstrate that the opposite is true.
Recommended Citation
Bell, Zoë, "Going Meta on the Minimum Circuit Size Problem: How Hard Is It to Show How Hard Showing Hardness Is?" (2021). HMC Senior Theses. 250.
https://scholarship.claremont.edu/hmc_theses/250
