This paper presents a new characterization of the class NP: a language L is in NP if and only if membership proofs for L can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof. The authors show that approximating clique and independent set problems is NP-hard, even in a weak sense. They also provide a new characterization of NP based on probabilistically checkable proofs (PCP), which has implications for the hardness of approximation. The paper discusses the implications of this characterization, including the NP-hardness of approximating the clique number within any constant factor. The authors also describe a technique for composing verifiers, which allows for more efficient verification procedures. The paper concludes with a proof of the main theorem, which states that NP is equal to PCP(log n, log n). This result has important implications for the study of complexity classes and the hardness of approximation.This paper presents a new characterization of the class NP: a language L is in NP if and only if membership proofs for L can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof. The authors show that approximating clique and independent set problems is NP-hard, even in a weak sense. They also provide a new characterization of NP based on probabilistically checkable proofs (PCP), which has implications for the hardness of approximation. The paper discusses the implications of this characterization, including the NP-hardness of approximating the clique number within any constant factor. The authors also describe a technique for composing verifiers, which allows for more efficient verification procedures. The paper concludes with a proof of the main theorem, which states that NP is equal to PCP(log n, log n). This result has important implications for the study of complexity classes and the hardness of approximation.