期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 \mathsfAM. This gives a `PCP characterization' of \mathsfAM analogous to the PCP Theorem for \mathsfNP. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, and for \mathsfPSPACE; however, we suggest that the result for \mathsfAM 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 \mathsfAM. Unfortunately, the hypotheses appear over-strong, and we present evidence against them. In the process we show that, if some language in \mathsfNP is hard-on-average against circuits of size 2(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.
关键词：Arthur-Merlin games, average case complexity, PCPs
