0
$\begingroup$

We know that SAT is an NP problem, so having the answer "yes, it's satisfiable" or "no, it's not satisfiable" requires the work of a non-deterministic Turing Machine with Polynomial execution time.

What about the cost to find the precise assignment $x_{solution}=(x_{1}=1,x_{2}=0...)$ ?

I'm a little bit confused about this. In an old example I found this algorithm in which we call SAT for each variable in the polynomial in order to find this assignment or similar.

Another question I have about SAT is for the #SAT problem (counting SAT), is it true that if a problem P is NP then P must be #P? (#P correspondent to NP but in counting problems).

Thank you!

$\endgroup$
1
  • $\begingroup$ You might want to explain what "SAT" is. $\endgroup$
    – robjohn
    May 31, 2020 at 22:33

1 Answer 1

1
$\begingroup$

Any algorithm $A$ for deciding SAT yields an almost as efficient algorithm $B$ for finding a satisfying truth assignment when one exists. Here "almost" means that $B$ involves running $A$ $n+1$ times when your input has $n$ variables in it. Here's how $B$ works:

Given a formula $\alpha(x_1,x_2,x_3,\dots,x_n)$ as input, first run $A$ to check whether $\alpha$ is satisfiable. If it isn't, then just output a message to that effect. From here on, my description of $B$ will assume that $\alpha$ is satisfiable.

Run $A$ on input $\alpha(\top,x_2,x_3,\dots,x_n)$, i.e., your original $\alpha$ with the first variable $x_1$ replaced by the symbol $\top$ for "true". So you're asking,$A$, in effect, whether $\alpha$ can be satisfied with $x_1$ set to true. If it can't, then it can certainly be satisfied with $x_1$ set to false, because we already know that $\alpha$ can be satisfied, and the only possible values for $x_1$ are $\top$ and $\bot$. So, whichever answer we get from this second run of $A$, we now know a specific truth value $v_1$ (either $\top$ or $\bot$) for $x_1$ such that $\alpha(v_1,x_2,x_3,\dots,x_n)$ is satisfiable.

Run $A$ on input $\alpha(v_1,\top, x_3,\dots,x_n)$. So we're committing ourselves to value $v_1$ for $x_1$ and asking $A$ whether $\alpha$ can still (i.e., subject to this commitment) be satisfied with $x_2$ getting the value "true". As in the preceding paragraph, whatever answer we get, we now know a value $v_2$ (either $\top$ or $\bot$) for $x_2$ such that $\alpha(v_1,v_2,x_3,\dots,x_n)$ is satisfiable.

Repeat the process for each of the remaining variables. (So the next run of $A$ uses input $\alpha(v_1,v_2,\top,x_4,\dots,x_n)$, and so forth.) We get, step by step, values $v_i$ for all the $x_i$'s such that, at the end, $\alpha(v_1,v_2,v_3,\dots,v_n)$ is satisfiable; that means it's satisfied, since there are no variables left.

$\endgroup$
1
  • $\begingroup$ Thank you!!!! :) $\endgroup$
    – Raydar
    Jun 1, 2020 at 7:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .