The paper presents a new characterization of NP in terms of probabilistic checkable proofs (PCP), improving upon previous work by Arora and Safra. The authors show that every language in NP has a probabilistic verifier that checks membership proofs using a logarithmic number of random bits and examines a constant number of bits in the proof. This result implies that no MAX SNP-hard problem has a polynomial-time approximation scheme unless NP = P. The paper also improves upon the clique hardness results of Feige et al. and Arora and Safra, showing that approximating the maximum clique size in an N-vertex graph to within a factor of N^ε is NP-hard for some constant ε. The main technical contributions involve constructing efficient verifiers that probabilistically check membership proofs for NP languages, using techniques similar to those in recent work on PCPs and recursive proof checking. The paper concludes with a discussion of related work and the implications of the main theorem for the hardness of approximating MAX 3-SAT.The paper presents a new characterization of NP in terms of probabilistic checkable proofs (PCP), improving upon previous work by Arora and Safra. The authors show that every language in NP has a probabilistic verifier that checks membership proofs using a logarithmic number of random bits and examines a constant number of bits in the proof. This result implies that no MAX SNP-hard problem has a polynomial-time approximation scheme unless NP = P. The paper also improves upon the clique hardness results of Feige et al. and Arora and Safra, showing that approximating the maximum clique size in an N-vertex graph to within a factor of N^ε is NP-hard for some constant ε. The main technical contributions involve constructing efficient verifiers that probabilistically check membership proofs for NP languages, using techniques similar to those in recent work on PCPs and recursive proof checking. The paper concludes with a discussion of related work and the implications of the main theorem for the hardness of approximating MAX 3-SAT.