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. Given a claimed solution x with length n, which might be false, the prover produces a proof "π" which states "x" solves L ("x" ∈ "L", the proof is a string ∈ Σ*). And the verifier is a randomized oracle Turing Machine "V" (the "verifier") that checks the proof "π" for the statement that "x" solves "L"(or "x" ∈ "L") and decides whether to accept the statement. The system has the following properties: