What are provers and verifiers in computation theory?

Question

Recently I was studying a computation and complexity theory on my own and I have a problem of grasping formally a concept of a prover and a verifier. I think I understand it on the intuitive level, but what exactly are they? A Turing machines (quantum, probabilistic if needed) with some restriction on verifier? Is it more general notion of some "abstract machines"? I would be grateful for a hint.

Answer 1

Given a decidable language $L$, we define a decider $V$ to be a verifier for $L$ if for each $w \in L$ exists a cerificate $c$ s.t. $<w,c> \in L(V)$.

Verifiers are particularly useful to give an alternative definition of the $NP$ class: $NP = \{L : L \in DEC \wedge \exists V \text{polinomial verifier for L}\}$. In this way, we can decide wether a language is in $NP$ by telling if a polinomial verifier exists for that language.

In practical terms, you can think of the certifier $c$ as a set of computational states $s_1, \ldots, s_n$ which occur during the computation of a NTM, in particular, these represent a branch of computation of the NTM. The verifier simulates the execution of that particular branch of the NTM.

If a polinomial verifier exists for a language $L$, it means that a NTM decides that language in polinomial time, hence $L \in NP$.