# Definition and example of search problem

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

WIKIPEDIA:

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.

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