期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that every language in NP has a probablistic verifier
that checks membership proofs for it using
logarithmic number of random bits and by examining a
constant number of bits in the proof.
If a string is in the language, then there exists a proof
such that the verifier accepts with probability 1 (i.e., for
every choice of its random string).
For strings not in the language, the verifier rejects
every provided ``proof" with
probability at least 1/2. Our result builds upon and improves a
recent result of Arora and Safra [FOCS 1992]
whose verifiers examine a nonconstant number of bits in the proof
(though this number is a very slowly growing function of the
input length).
As a consequence we prove that no MAX SNP-hard problem has a
polynomial time approximation scheme, unless NP=P. The class
MAX SNP was defined by Papadimitriou and Yannakakis [JCSS 1991]
and hard
problems for this class include vertex cover, maximum satisfiability,
maximum cut, metric TSP, Steiner trees and shortest superstring.
We also improve upon the clique hardness results of Feige, Goldwasser,
Lovasz, Safra and Szegedy [JACM 1996], and Arora and Safra [FOCS 1992]
and show that there exists a positive such that
approximating the maximum clique size in an N-vertex
graph to within a factor of N^{\epsilon} is NP-hard.
(An extended abstract of this paper appeared in FOCS 1992.
This is the full version.)
关键词：Approximation, complexity, NP-completeness, optimization, probabilisitic checking of proofs (PCP)
