1
$\begingroup$

The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time.

My question is, if asking for an algorithm that only provides yes/no, or solvable/not solvable, without providing an exact solution of the 3-SAT formula, will this result in another complexity class?

The reason I have in mind of asking this, is a similar situation when looking for prime numbers and factorizations. Where it is known that it's much easier to test if a number is a prime number yes/no, than to find an exact prime factorization of a number.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression true, it here are any). Thus the cost of the search problem isn't "too much more" (multiply by the size of the input --number of variables-- is polynomial).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Check Belare and Goldwasser, "The complexity of decision versus search", SIAM J. Of Computing, 23:1 (feb 1994), pp. 97-119. Belare has notes for a class.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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