The Power of Natural Properties as Oracles

Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich

Abstract

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-theoretic results that use the $SAT$ oracle, one can use the $MCSP$ oracle instead. For example, we show that \( ZPEXP^{MCSP}\not\subseteq P/poly, \) which should be contrasted with the previously known circuit lower bound $ZPEXP^{NP}\not\subseteq P/poly$. We also show that, assuming the existence of Indistinguishability Obfuscators (IO), $SAT$ and $MCSP$ are equivalent in the sense that one has a $ZPP$ algorithm if and only the other one does. We interpret our results as providing some evidence that $MCSP$ may be $NP$-hard under randomized polynomial-time reductions.

Versions