Probabilistic Soundness

Jump to navigation Jump to search

A Probabilistic Soundness is a Rationality Criterion that ...



  • (Wikipedia, 2019) ⇒ Retrieved:2019-6-14.
    • 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 (xL, 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 xL) and decides whether to accept the statement. The system has the following properties:
      • Completeness: For any xL, given the proof π produced by the prover of the system, the verifier accepts the statement with probability at least c(n),
      • Soundness: For any xL, then for any proof π, the verifier mistakenly accepts the statement with probability at most s(n).