Home > Term: probabilistically checkable proof
probabilistically checkable proof
An interactive proof system in which provers follow a fixed strategy, that is, one not affected by any messages from the verifier. The prover's strategy for a given instance x of a decision problem can be represented by a finite oracle language Bx, which constitutes a proof of the correct answer for x.
- Part of Speech: noun
- Industry/Domain: Computer science
- Category: Algorithms & data structures
- Government Agency: NIST
0
Creator
- GeorgeV
- 100% positive feedback