I am reading about Boolean Satisfiability Problem and Nondeterministic Algorithms, in the latter defination it says :

In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations $...$ These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path

Assume we have a Non-deterministic algorithm for (SAT), does that mean the algorithm will show some computational paths leading to incorrect solutions (Non Satisfying Assignments) and other computational paths leading to correct solutions (Satisfying Assignment) ?

Or it is supposed to show only the correct solutions ?


Usually, when one develops an algorithm, there is a proof of correctness. From what I know, "nondeterministic" means the algorithm may or may not give you the correct answer, but it will definitely not give you an incorrect one.

| cite | improve this answer | |

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.