patternMinor
NP-hardness of MCSP
Viewed 0 times
mcsphardnessstackoverflow
Problem
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?
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?
Solution
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).
Context
StackExchange Computer Science Q#82768, answer score: 2
Revisions (0)
No revisions yet.