#### Title

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 2* ^{n}*. 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 ⊈ Σ_{k}P/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