Nondeterministic Algorithms [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be开发者_如何学编程 reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

I need a simple description of nondeterministic algorithms . Can we comapre nondeterministic algorithm with computer with parrallel processor? please someone exactly explain me about nondeterministic algorithms

---

a non deterministic algorithm is an algorithm ran on a non deterministic turing machine.
each calculation in this algorithm can branch into 2 calculations, which are computed simultaneously.

none deterministic algorithm example:
Set Cover: "guess" a subset of the vertices, and check if it is a valid cover.
the guessing is: for each element: check one possibility it IS in the set and it is NOT in the set.

It is not parallel processor, because in here (nondeterministic algorithm), the number of branches is not limited, while in parallel processor it is. In parallel computing, you are still bounded to do the 2^n OPs for finding vertex coverage, while in nondeterministic algorithm, you are doing only n ops, with n different branches.

a non-deterministic machine would be more like quantum computer, than parallel processing. [note that quantum computer is still 'weaker' then non-deterministic turing machine, assuming P!=NP, of course].