NP-completeness is a category of decision problems, that is, problems in which the answer is Yes or No. When we say that 3SAT is NP-complete, what we mean is that the decision version of 3SAT is NP-complete.
There are other types of problems around. The three most common ones are optimization problems, function problems and search problems.
Optimization problems: These are problems in which the aim is to maximize or minimize some quantity. The decision problem associated with a maximization problem has as input an instance $I$ of the optimization problem and a threshold $\theta$, and it asks whether there is a solution for $I$ whose value is at least $\theta$. The way we framed the problem guarantees that (in most common cases) the decision problem is in NP. In many cases, the decision problem is NP-hard, and in these cases we also sometimes say that the optimization problem is NP-hard, though this is abuse of notation.
There is a simple way to reduce the optimization problem to the decision problem (that is, a way to solve the optimization problem if you can solve the decision problem): binary search. Assuming that you know lower and upper bounds on the possible answer (this is the case for many problems), you simply perform binary search using the decision oracle. In many cases, the number of steps you have to perform is at most polynomial.
Function problems: These are problems in which the goal is to compute some function of the input. Decision problems are a special case, in which the function returns either "Yes" or "No". We can always formulate function problems as decision problems, using an encoding trick: given an input and an index $i$, the decision problems asks us to find the value of the $i$th bit of the output of the function.
Search problems: These are problems which are like the "solution" version of 3SAT: given an instance, there are zero or more solutions, and we are interested in finding whether there is at least one solution, and if so, one of the solutions. An important subclass is that of total search problems, in which a solution is guaranteed to exist. Function problems are a special case in which the solution is unique. Total search problems have lately been popular in communication complexity.
With each search problem we can associate a decision problem, which asks whether a solution exists or not. Many problems exhibit the phenomenon of self-reducibility, in which the search problem reduces to the associated decision problem. This is the case for 3SAT. The idea is very simple. Given a satisfiable 3CNF $\phi$, we execute the following recursive procedure:
- Pick a variable $x$ occurring in $\phi$ (if $\phi$ involves no variables, return immediately).
- Substitute $x = F$ to obtain a formula $\phi_{x=F}$. If $\phi_{x=F}$ is satisfiable (this can be determined using a decision oracle), recursively determine a satisfying assignment for $\phi_{x=F}$, and add to it $x=F$.
- If $\phi_{x=F}$ is not satisfiable, do the same for $\phi_{x=T}$ (which must be satisfiable).
You can check that for a formula involving $n$ variables, there are at most $2n$ recursive calls, so this is an efficient reduction.
