Search problems

A problem is a search problem if we can verify a solution in polynomial time.

Formally:

The problem is of the form, for a given instance $I$ of the problem you can either:

• find a solution $S$ for $I$ if one exists, or
• output no if $I$ has no solutions.

Then this problem is a search problem if given an instance $I$ and a solution $S$ then we can verify that $S$ is a solution to $I$ in polynomial time in $\vert I \vert$.