Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems

摘要: The definition of the class NP (Coo71, Lev73) highlights problem verification proofs as one central interest to theoretical computer science. Recent efforts have shown that efficiency can be greatly improved by allowing verifier access random bits and accepting probabilistic guarantees from (BFL91, BFLS91, FGL$\sp+$91, AS92). We improve upon proof systems developed above obtain which verified probabilistically examining only a constant number (randomly chosen) proof. The efficiently verifiable constructed here rely on structural properties low-degree polynomials. explore these functions some simple basic questions about them. consider form: (1) (testing) Given an oracle for function f, is f close polynomial? (2) (correcting) Let polynomial g, it possible reconstruct value g any given input using f? The described been raised before in context coding theory problems error-detecting error-correcting codes. More recently such has regenerated due its connections with area program result checking. use results starting point combine several algorithmic techniques including pairwise independent sampling give efficient randomized algorithms tasks. As consequence we fast error-detection error-correction well-known codes. The expressive nature polynomials suffices capture complexity translate our testing correcting procedures into two different deciding membership languages. One system generates small somewhat other very large but proofs. then employ new paper (AS92) compose probing them just bits. An important this NP-complete optimization problems, finding even approximate solutions NP-hard problem. particular MAX SNP, introduced Papadimiatriou Yannakakis (PY91). For every SNP-hard show there $\epsilon$, approximating optimum within relative error $\epsilon$ NP-hard.