Computer Science – Computational Complexity
Scientific paper
2010-02-19
Computer Science
Computational Complexity
18 pages
Scientific paper
We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class AM. This gives a `PCP characterization' of AM analogous to the PCP Theorem for NP. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, and for PSPACE; however, we suggest that the result for AM might be of particular significance for attempts to derandomize this class. To test this notion, we pose some `Randomized Optimization Hypotheses' related to our stochastic CSPs that (in light of our result) would imply collapse results for AM. Unfortunately, the hypotheses appear over-strong, and we present evidence against them. In the process we show that, if some language in NP is hard-on-average against circuits of size 2^{Omega(n)}, then there exist hard-on-average optimization problems of a particularly elegant form. All our proofs use a powerful form of PCPs known as Probabilistically Checkable Proofs of Proximity, and demonstrate their versatility. We also use known results on randomness-efficient soundness- and hardness-amplification. In particular, we make essential use of the Impagliazzo-Wigderson generator; our analysis relies on a recent Chernoff-type theorem for expander walks.
No associations
LandOfFree
A PCP Characterization of AM does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A PCP Characterization of AM, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A PCP Characterization of AM will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-363229