Search problem
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
of the problem you can either:
- find a solution
for if one exists, or - output no if
has no solutions. Then this problem is a search problem if given an instance
and a solution then we can verify that is a solution to in polynomial time in .