Definition and example of search problem

Question

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.

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