# Probabilistic Soundness

A Probabilistic Soundness is a Rationality Criterion that ...

## References

### 2019

• (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Probabilistically_checkable_proof#Definition 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).