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