Non-black-box worst-case to average-case reductions within NP
S Hirahara - 2018 IEEE 59th Annual Symposium on …, 2018 - ieeexplore.ieee.org
S Hirahara
2018 IEEE 59th Annual Symposium on Foundations of Computer Science …, 2018•ieeexplore.ieee.orgThere are significant obstacles to establishing an equivalence between the worst-case and
average-case hardness of NP: Several results suggest that black-box worst-case to
averagecase reductions are not likely to be used for reducing any worstcase problem
outside coNP to a distributional NP problem. This paper overcomes the barrier. We present
the first nonblack-box worst-case to average-case reduction from a problem outside coNP
(unless Random 3SAT is easy for coNP algorithms) to a distributional NP problem …
average-case hardness of NP: Several results suggest that black-box worst-case to
averagecase reductions are not likely to be used for reducing any worstcase problem
outside coNP to a distributional NP problem. This paper overcomes the barrier. We present
the first nonblack-box worst-case to average-case reduction from a problem outside coNP
(unless Random 3SAT is easy for coNP algorithms) to a distributional NP problem …
There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to averagecase reductions are not likely to be used for reducing any worstcase problem outside coNP to a distributional NP problem. This paper overcomes the barrier. We present the first nonblack-box worst-case to average-case reduction from a problem outside coNP (unless Random 3SAT is easy for coNP algorithms) to a distributional NP problem. Specifically, we consider the minimum time-bounded Kolmogorov complexity problem (MINKT), and prove that there exists a zero-error randomized polynomial-time algorithm approximating the minimum time bounded Kolmogorov complexity k within an additive error ̅O(√ k) if its average-case version admits an errorless heuris tic polynomial-time algorithm. (The converse direction also holds under a plausible derandomization assumption.) We also show that, given a truth table of size 2 n approximating the minimum circuit size within a factor of 2( 1-ε jn is in BPP for some constant € > 0 if and only if its average-case version is easy. Based on our results, we propose a research program for excluding Heuristica, i.e., establishing an equivalence between the worst-case and average-case hardness of NP through the lens of MINKT or the Minimum Circuit Size Problem (MCSP).
ieeexplore.ieee.org