# Question about SAT and assignment

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!

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

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.