Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR09-139 | 6th November 2010 13:45

On the Power of Randomized Reductions and the Checkability of SAT

RSS-Feed




Revision #3
Authors: Mohammad Mahmoody, David Xiao
Accepted on: 6th November 2010 13:45
Downloads: 1717
Keywords: 


Abstract:

We prove new results regarding the complexity of various complexity classes under randomized oracle reductions. We first prove that $BPP^{prSZK} \subseteq AM \cap coAM$, where $prSZK$ is the class of promise problems having statistical zero knowledge proofs. This strengthens the previously known facts that $\prSZK$ is closed under $NC^1$ truth-table reductions (Sahai and Vadhan, J. ACM '03) and that $P^{prSZK} \subseteq AM \cap coAM$ (Vadhan, personal communication). Our results imply that for most cryptographically interesting lattice problems, there is a sharp threshold for the approximation factor below which we do not know if the problems are even in $AM$, while above which the problems are in $AM \cap coAM$ not only via Karp reductions but also via randomized oracle reductions.

Then we investigate the power of randomized oracle reductions with relation to the notion of instance checking (Blum and Kannan, J. ACM '95). We observe that a theorem of Beigel implies that if any problem in $TFNP$ such as Nash equilibrium is $NP$-hard under randomized oracle reductions, then $SAT$ is checkable.

We also observe that Beigel's theorem can be extended to an average-case setting by relating checking to the notion of program testing (Blum et al., JCSS '93). From this, we derive that if one-way functions can be based on $NP$-hardness via a randomized oracle reduction, then $SAT$ is checkable. By showing that $NP$ has a \emph{non-uniform} tester, we also show that worst-case to average-case randomized oracle reduction for any relation (or language) $R \in NP$ implies that $R$ has a non-uniform instance checker. These results hold even for adaptive randomized oracle reductions.



Changes to previous version:

Introduction modified to include more intuition and motivation.


Revision #2 to TR09-139 | 30th December 2009 19:28

On the Power of Randomized Reductions and the Checkability of SAT





Revision #2
Authors: Mohammad Mahmoody, David Xiao
Accepted on: 30th December 2009 19:28
Downloads: 1608
Keywords: 


Abstract:

The closure of complexity classes is a delicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions are allowed to be randomized.

We first prove that $BPP^{SZK} \subseteq AM \cap coAM$, strengthening the previously known facts that $SZK$ is closed under $NC^1$ truth-table reductions (Sahai and Vadhan, J. ACM '03) and that $P^{SZK} \subseteq AM \cap coAM$ (Vadhan, as cited in Goldreich, ECCC '05). Our proof relies on showing that a certain class of real-valued functions that we call $RTFAM$ can be computed using an $AM$ protocol.

Then we investigate the power of randomized oracle reductions with relation to the notion of program checking (Blum and Kannan, J. ACM '95). We observe that a theorem of Beigel implies that if any problem in $TFNP$ such as Nash equilibrium is $NP$-hard under randomized oracle reductions, then $SAT$ is checkable.

We also observe that Beigel's theorem can be extended to an average-case setting by relating checking to the notion of program \emph{testing} (Blum et al., JCSS '93). From this, we derive that if one-way functions can be based on $NP$-hardness via a randomized oracle reduction, then $SAT$ is checkable. By showing that $NP$ has a \emph{non-uniform} tester, we also show that if $SAT$ has a worst-case to average-case randomized oracle reduction, then $SAT$ is checkable with a non-uniform instance checker. These results hold even for adaptive randomized oracle reductions.



Changes to previous version:

Acknowledgements added.


Revision #1 to TR09-139 | 26th December 2009 03:20

On the Power of Randomized Reductions and the Checkability of SAT





Revision #1
Authors: Mohammad Mahmoody, David Xiao
Accepted on: 26th December 2009 03:20
Downloads: 1663
Keywords: 


Abstract:

The closure of complexity classes is a delicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions are allowed to be randomized.

We first prove that $BPP^{SZK} \subseteq AM \cap coAM$, strengthening the previously known facts that $SZK$ is closed under $NC^1$ truth-table reductions (Sahai and Vadhan, J. ACM '03) and that $P^{SZK} \subseteq AM \cap coAM$ (Vadhan, as cited in Goldreich, ECCC '05). Our proof relies on showing that a certain class of real-valued functions that we call $RTFAM$ can be computed using an $AM$ protocol.

Then we investigate the power of randomized oracle reductions with relation to the notion of program checking (Blum and Kannan, J. ACM '95). We observe that a theorem of Beigel implies that if any problem in $TFNP$ such as Nash equilibrium is $NP$-hard under randomized oracle reductions, then $SAT$ is checkable.

We also observe that Beigel's theorem can be extended to an average-case setting by relating checking to the notion of program \emph{testing} (Blum et al., JCSS '93). From this, we derive that if one-way functions can be based on $NP$-hardness via a randomized oracle reduction, then $SAT$ is checkable. By showing that $NP$ has a \emph{non-uniform} tester, we also show that if $SAT$ has a worst-case to average-case randomized oracle reduction, then $SAT$ is checkable with a non-uniform instance checker. These results hold even for adaptive randomized oracle reductions.



Changes to previous version:

Typos fixed (in the abstract above and in the proof of Theorem 1.1)


Paper:

TR09-139 | 17th December 2009 19:27

On the Power of Randomized Reductions and the Checkability of SAT





TR09-139
Authors: Mohammad Mahmoody, David Xiao
Publication: 18th December 2009 11:35
Downloads: 1890
Keywords: 


Abstract:

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions are allowed to be randomized.

We first prove that $BPP^{SZK} \subseteq AM \cap coAM$, strengthening the previously known facts that $SZK$ is closed under $NC^1$ truth-table reductions (Sahai and Vadhan, J. ACM '03) and that $P^{SZK} \subseteq AM \cap coAM$ (Vadhan, as cited in Goldreich, ECCC '05). Our proof relies on showing that a certain class of real-valued functions that we call $RTFAM$ can be computed using an $AM$ protocol.

Then we investigate the power of randomized oracle reductions with relation to the notion of program checking (Blum and Kannan, J. ACM '95). We observe that a theorem of Beigel implies that if any problem in $TFNP$ such as Nash equilibrium is $NP$-hard under randomized oracle reductions, then $SAT$ is checkable.

We also observe that Beigel's theorem can be extended to an average-case setting by relating checking to the notion of program \emph{testing} (Blum et al., JCSS '93). From this, we derive that if one-way functions can be based on $NP$-hardness via a randomized oracle reduction, then $SAT$ is checkable. By showing that $NP$ has a \emph{non-uniform} tester, we also show that if $SAT$ has a worst-case to average-case randomized oracle reduction, then $SAT$ is checkable with a non-uniform instance checker. These results hold even for adaptive randomized oracle reductions.



ISSN 1433-8092 | Imprint