4
$\begingroup$

I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms do not rely on any randomness whatsoever? In which case, this Wikipedia article which mentions Fermat's little theorem includes generating random numbers. I had thought that non-determinism was more of a concept than one that could be put into practice at this given moment - so what exactly are the 'non-deterministic algorithms' on the Internet, such as on the Wiki page above?

Furthermore, D. Harel's book Algorithmics introduces non-determinism in that whenever the machine must make a choice between two or more branches to next states, it ALWAYS picks the one which will lead to an accepting state, if there are any accepting states. In this way, how can non-deterministic algorithms exist on current machines, as they don't have 'insight' as to what will happen further down the line?

Finally, does converting from a non-deterministic FSM to a deterministic FSM take an exponential amount of time? If not, what bearing would this have on the P=NP problem?

$\endgroup$
3
$\begingroup$

Is it right that non-deterministic algorithms do not rely on any randomness whatsoever?

Yes and no. Non-determinism just means that there in the computation there is a choice that needs to be made based on information not available to the algorithm. There are multiple solutions to this choice, one of which is randomness - for example in random pivot quicksort.

I had thought that non-determinism was more of a concept than one that could be put into practice at this given moment - so what exactly are the 'non-deterministic algorithms' on the Internet, such as on the Wiki page above?

Furthermore, D. Harel's book Algorithmics introduces non-determinism in that whenever the machine must make a choice between two or more branches to next states, it ALWAYS picks the one which will lead to an accepting state, if there are any accepting states. In this way, how can non-deterministic algorithms exist on current machines, as they don't have 'insight' as to what will happen further down the line?

There are four main approaches (to my knowledge) for dealing with non-determinism: parallelism, randomness, backtracking and superstates.

  1. Parallelism: whenever a choice needs to be made split the program and investigate all choices in parallel.

  2. Randomness: use randomness to choose a single choice out of all.

  3. Backtracking: deterministically choose a choice (e.g. the first one) and continue computation with that choice. When that choice wasn't correct go back and choose the second options, etc.

  4. Superstates: track all possible states the program can be in, and whenever input is received apply that input to all possible states, merging states and rejecting states eagerly.

Note that not all approaches are always valid and/or feasible. Parallelism is rarely feasible as it requires a lot of physical resources and not much non-determinism, randomness is only correct if each choice is correct, and it's just a matter of performance.

To directly implement a NFA either 3 or 4 is used. Another example of 4 are full CFG parsers that can handle ambiguity such as an Earley parser.

Finally, does converting from a non-deterministic FSM to a deterministic FSM take an exponential amount of time?

By necessity, because the resulting output can have an exponential number of states.

$\endgroup$
  • $\begingroup$ Thank you. So I understand that the magical non-determinism is impossible? I would also like to ask further how backtracking counts as non-determinism - is the whole point that the computer makes a choice when having multiple paths? Wikipedia's definition of non-deterministic: a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs - does behaviour here count the exact lines of code which are executed, as well as the output? $\endgroup$ – Schmetterling Aug 1 '18 at 15:29

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.