00000cab a22000003a 4500 UP-99796217608727529 Buklod 20231007234724.0 m |o d | ta 090226s xx d | ||r ||||| || (iLib)UPD-00077096442 DENGII eng Arora, Sanjeev Probabilistic checking of proofs a new characterization of NP. pp. 70-122 We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof.We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard. Theory of computation. Computation by abstract devices. Analysis of algorithms and problem complexity. Mathematical logic and formal languages. Algorithms. Theory. Verification. Journal of the ACM 45, 1 (1998). FO UPD DENG-II Article