- The Non-Hardness of Approximating Circuit Size
- Project Year:
2018
- REU Student (s):
Rahul Ilango | Rutgers University
| Neekon Vafa | Harvard University MA
- Student 1 Institution:
Rutgers University-New Brunswick
- Student 2 Institution:
Harvard University
- Project Mentor:
Eric Allender
- Project Mentor Area:
Computer Science
- Project Abstract:
Understanding the computational difficulty of the Minimum Circuit Size Problem (MCSP) dates back to the 1950s and has wide-ranging implications in theoretical computer science. Since MCSP is not known to be NP-hard and is believed not to be in P, it is seen as a promising NP-intermediate candidate. However, despite extensive study of MCSP, there is little evidence that it is not NP-hard. In a recent development, Murray and Williams show that MCSP is not NP-hard under TIME(n0.49) projections. Murray and Williams also conjecture that MCSP is not NP-hard under logtime-uniform AC0 reductions. We show that any super-constant multiplicative approximation of MCSP is not hard for NP (in fact, not hard for PARITY) under even non-uniform AC0 many-one reductions. This result is surprising (and nearly tight) because Allender and Hirahara show that there is a constant-factor approximation to MKTP, a problem closely related to MCSP, that is hard for PARITY under non-uniform NC0 many-one reductions. To much frustration, this PARITY hardness result is not known for MCSP, and we show that the natural way to extend it to MCSP is actually impossible.
