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


Any decidable problem can be solved by a deterministic algorithm. The thing about SAT (and any other NP-complete problem) is that we don't know any efficient deterministic algorithm that solves it, and we think there might not even be one.

  • $\begingroup$ So, Assuming there is an efficient deterministic & non-deterministic algorithm for SAT, and there exists multiple Accepting Solutions for a given Boolean Formula. Are we interested in having all the (Accepting States) therefore use the nondeterministic algorithm or we only (any) accepting state therefore use the determinsitc algorithm ? $\endgroup$ – Jacob Billerchy Sep 21 '18 at 0:57
  • $\begingroup$ The deterministic nature of algorithm has nothing to do with how many solutions we want. Also, I don't think we ever need many solutions for SAT. We are only interested in whether it is satisfiable or not. $\endgroup$ – Sandro Lovnički Sep 21 '18 at 1:04
  • $\begingroup$ @SandroLovnički Yes i understand that we are interested in knowing if the given Boolean Formula evalutes to true or false but is it the case that we later might apply constraints to choose a solution evaluating to (true) among the multiple solutions that evaluate to (true) as a sort of extra optimization ? $\endgroup$ – Jacob Billerchy Sep 21 '18 at 1:58
  • $\begingroup$ s/think there might not even be one/are reasonably sure there is not one/. $\endgroup$ – R.. GitHub STOP HELPING ICE Sep 21 '18 at 3:05
  • $\begingroup$ @JacobBillerchy SAT is the following problem. We are given a Boolean formula as input. We must say "yes" if there is an assignment to the variables that makes the formula true, and "no" if there is no such assignment. The "solution" to an instance of the problem is just "yes" or "no". This problem is defined independently of any algorithm that might solve it. Having multiple algorithms is not the same as having multiple solutions. Evaluating a formula, given values of the variables, is a much simpler problem: we already know efficient algorithms for that, but that is not SAT. $\endgroup$ – David Richerby Sep 21 '18 at 9:12

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.

  • $\begingroup$ So how can we distinguish between an implentation of a non-deterministic algorithm simulated on a deterministic algorithm and another (pure) deterministic algorithm ? $\endgroup$ – Jacob Billerchy Sep 21 '18 at 0:40
  • $\begingroup$ Most formally, we cannot. Detecting equality (or any non-trivial property) of algorithms is undecidable. But why would you do that? We write algorithms, therefore we know what we meant for it to do. I don't think there will be a situation that an algorithm pops into existance and asks you to figure out what it is :) $\endgroup$ – Sandro Lovnički Sep 21 '18 at 0:46
  • $\begingroup$ Specifically, in this case, (pure) deterministic algorithm will be implemented similarly like a deterministic algorithm simulating non-deterministic algorithm. (pure) needs to test all $2^n$ possibilities and simulation needs to simulate all non-deterministic branchings. Non-deterministic algorithm still goes through all $2^n$ possibilities, it just does many at once. And I repeat, this is theoretical. If we had real (physicaly working) non-deterministic algorithms, $P \neq NP$ would not be a problem of major concern. $\endgroup$ – Sandro Lovnički Sep 21 '18 at 0:55
  • $\begingroup$ Because the Deterministic (D) & Non-Determinsitic (ND) concepts are confusing. My understanding is that D will reach an (Accept / Reject) state, while a ND algorithm will have (if exists) mulitple states of (Accept / Reject). When a ND is simulated on D it will show mulitple states of (Accept / Reject), how come that D shows mulitple (Accept / Reject) states, that will contradict its defination not have a single (Accept / Reject) state ? Or is it the case that those mulitple states of (Accept / Reject) are the equivalent of the (Accept / Reject) state of the simulated D ? $\endgroup$ – Jacob Billerchy Sep 21 '18 at 1:45

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.