Definition and example of search problem
Here is an example of a search problem:


  Given a CNF $\varphi$, find a satisfying assignment $x$.


Every satisfying assignment would do. A machine solves this problem if on input $\varphi$:


If $\varphi$ is satisfiable, then the machine outputs a satisfying assignment.
If $\varphi$ is unsatisfiable, then the machine outputs "unsatisfiable".


An important class of search problems are those that always have solutions. Here is a canonical example:


  Given an unsatisfiable CNF $\varphi$ and an assignment $x$, find a clause not satisfied by $x$.


Note that since $\varphi$ is unsatisfiable, for every assignment there is a clause which $x$ doesn't satisfy. A machine solves this problem if given $\varphi$ and $x$, it outputs a clause of $\varphi$ unsatisfied by $x$.