Complexity theory makes a key distinction between decidability and verifiability. A decision problem is said to be polynomial-time decidable, as we have discussed, if there is a polynomial-time algorithm that will correctly answer instances of it. A decision problem A is polynomial-time verifiable, in contrast, if there is a polynomial-time algorithm p, such that x ∈ A if and only if there is a companion witness w, of polynomial-size in x, such that p accepts (x, w). In effect, the right witness w can provide the extra information enabling positive instances of x ∈ A to be verified as correct.
...more
