Probabilistically checkable proof
Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used.Given a decision problem L (or a language L with its alphabet set Σ), a probabilistically checkable proof system for L with completeness c(n) and soundness s(n), where 0 ≤ s(n) ≤ c(n) ≤ 1, consists of a prover and a verifier.The system has the following properties: For the computational complexity of the verifier, the verifier is polynomial time, and we have the randomness complexity r(n) to measure the maximum number of random bits that V uses over all x of length n and the query complexity q(n) of the verifier is the maximum number of queries that V makes to π over all x of length n. In the above definition, the length of proof is not mentioned since usually it includes the alphabet set and all the witnesses.The theory of probabilistically checkable proofs studies the power of probabilistically checkable proof systems under various restrictions of the parameters (completeness, soundness, randomness complexity, query complexity, and alphabet size).The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992,[2] although their properties were studied earlier.[2][4] The theory of hardness of approximation requires a detailed understanding of the role of completeness, soundness, alphabet size, and query complexity in probabilistically checkable proofs.