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?

  • $\begingroup$ Please include links to the papers you mention. The first one, by the way, has a coauthor, Cody D. Murray. $\endgroup$ – Yuval Filmus Oct 21 '17 at 5:47
  • $\begingroup$ 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)? $\endgroup$ – D.W. Oct 21 '17 at 5:50
  • $\begingroup$ @YuvalFilmus Sure. It was an honest mistake. I have corrected it. $\endgroup$ – Pawan Kumar Oct 22 '17 at 3:24
  • $\begingroup$ @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. $\endgroup$ – Pawan Kumar Oct 22 '17 at 3:27

The footnote mentions an earlier unpublished result which is superseded by a result proved in the paper.


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).

  • $\begingroup$ 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. $\endgroup$ – Pawan Kumar Oct 22 '17 at 3:34
  • $\begingroup$ Al algorithm running in polylogarithmic time doesn't necessarily use only logarithmic space. $\endgroup$ – Yuval Filmus Oct 22 '17 at 6:34
  • $\begingroup$ Agreed sir. But, the ultimate question remains. In Murray, Williams paper, Local reductions are ruled out, but TIME(poly(log n)) reductions are not. (as written in the footnote of page 368). In other words, MCSP are not NP-hard under local reductions while they still could be NP-hard under TIME(poly(log n)) reductions. Now, this is the part I am stuck in. Local reductions allows more time for each output bit than TIME(poly(log n)) reductions. So, how is that possible? $\endgroup$ – Pawan Kumar Oct 22 '17 at 9:24
  • $\begingroup$ Theorem 1.2 in Murray & Williams is about reductions from PARITY, not NP-hardness reductions. Can you state clearly which two statements you find conflicting? $\endgroup$ – Yuval Filmus Oct 22 '17 at 10:12
  • $\begingroup$ 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? $\endgroup$ – Pawan Kumar Oct 23 '17 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.