Why SAT Requires A Non-determinstic Algorithm? I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).

I do understand the difference between a Deterministic and Non-Deterministic Algorithm, however i don't understand why SAT requires a Non-Determinsitic Algorithm ? Why not a Deterministic Algorithm ?

How do we know for sure that a problem requires a Deterministic or Non-Deterministic Algorith that solves it ? (if it was solvable, i,e. not undecidable problem).
It is not true that it requires a non-deterministic algorithm.

You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).

However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of NP problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.



All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.