CS341 Study Guide - Co-Np, Parameterized Complexity, Computational Problem
Document Summary
A decision problem is a parameterized problem with a yes/no answer. Furthermore, for each yes instance i, there must be at least one valid certificate, and for each no instance there must be no valid certificates at all. If, further, v runs in time bounded by a polynomial in the size of i, then it is called a polynomial-time verifier. A decision problem is in np if it has a polynomial-time verifier. Note that every problem in p is also in np in a trivial sense: we can solve the problem in polynomial-time without even looking at c. A polynomial-time verifier takes i = g and c = a claimed list of the vertices forming the cycle as input. It then checks to ensure that all vertices are represented and the edges actually exist in g. A polynomial-time verifier takes i = n and c = (a,b) as input.
