I searched the pages a lot about the search problem but didn't understand much, so please make it clearer for me.


In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If R is a binary relation such that field(R) ⊆ Γ+ and T is a Turing machine, then T calculates R if:

If x is such that there is some y such that R(x, y) then T accepts x with output z such that R(x, z) (there may be multiple y, and T need only find one of them) If x is such that there is no y such that R(x, y) then T rejects x

If anyone can explain it to me easily and give a few examples, it will help me a lot.


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.