# NP-hardness of MCSP

Ryan Williams and Cody Murray in 2015 proved that MCSP (Minimum Circuit Size Problem) is provably not NP-hard under local reductions. (Local reductions are the ones in which you are allowed time $O(n^{1/2} - \epsilon))$. He has done it by showing even stronger statement that: Even Parity can't reduced to MCSP using local reductions. In the same paper, he has mentioned in footnotes that "Dhiraj Holden and Chris Umans (personal communication) proved independently that there is no TIME(poly(logn)) reduction from SAT to MCSP unless NEXP $\subseteq \Sigma_{2}^{P}$".

The problem is: $TIME(poly(log n))$ is much smaller than $O(n^{1/2} - \epsilon)$ for any $\epsilon$. (Since you are allowed only poly(log n) time to calculate each bit of output instead of $O(n^{1/2} - \epsilon)$). So, If MCSP is not locally hard(unconditionally), then how come under the much stricter reduction $TIME(poly(log n))$, it is still possible to prove MCSP is NP-hard?

• Please include links to the papers you mention. The first one, by the way, has a coauthor, Cody D. Murray. – Yuval Filmus Oct 21 '17 at 5:47
• What's MCSP? Can you spell out the acronym? Can you provide a full citation to all papers you refer to (authors, title, where published, and link to freely available pdf, if available)? – D.W. Oct 21 '17 at 5:50
• @YuvalFilmus Sure. It was an honest mistake. I have corrected it. – Pawan Kumar Oct 22 '17 at 3:24
• @D.W. MCSP is Minimum Circuit Size Problem. we are given (T,k) where T is truth-table of a boolean function and k is a positive integer (encoded in binary or unary), and the goal is to determine if T is the truth table of a Boolean function with circuit complexity at most k. The links to the papers have been updated too. – Pawan Kumar Oct 22 '17 at 3:27

The reductions considered by Murray and Williams are local: each bit of the output can be computed in time $O(n^{1/2-\epsilon})$ (on a RAM). In contrast, Allender et al. consider logspace reductions, in which each bit can be computed in logarithmic space. The latter notion of reductions is stronger since an algorithm running in space $C\log n$ could run in time $n^C$, where $C$ is an arbitrary constant (which could be larger than 1/2).
• Yes. Correct. But In Murray, Williams paper cited above on page 368, they have mentioned in Footnotes the following: Dhiraj Holden and Chris Umans (personal communication) proved independently that there is no TIME(poly(logn)) reduction from SAT to MCSP unless $NEXP \subseteq \Sigma_{2}^{P}$. The proof is not given, but can be easily done. Start with succ. SAT and use TIME(poly(logn)) to reduce to succ. MCSP, which implies NEXP collapses to $\Sigma_{2}^{P}$. This is where the problem lies. TIME(poly(logn)) is surely stricter reduction than Local reduction and is yet not ruled out. – Pawan Kumar Oct 22 '17 at 3:34
• Sure sir. On page 368: Theorem 1.2 says that PARITY can't be reduced to MCSP under local reductions. (which means that MCSP is not $AC^{0}[2]$ hard under local reductions) Now, in the footnotes on the same page on 368, it is said that If MCSP is NP-hard under TIME(poly(log n)) reductions, then NEXP $\subseteq \Sigma_{2}^{P}$. My confusion is: If MCSP is not $AC^{0}[2]$ hard under local reduction, then surely it is not NP hard under local reduction too. (Since $AC^{0}[2] \subset NP$ )Still, it is possible to prove MCSP is NP-hard under TIME(poly(log n)) reductions. Am I missing something? – Pawan Kumar Oct 23 '17 at 4:43