Given a problem instance I, find a solution S, or determine that there is no such solution.
For a search problem to be well-posed, we require that a proposed solution can be checked quickly for correctness.
- S has a length that is bounded by a polynomial in the input size n
- There is a polynomial-time algorithm that takes as input I and S and determines whether or not S is a solution to I.