What is Nondeterminism?
Determinism is the property of a process or algorithm that at any point during the process, given the same state and same input, the next step will always be the same and unique. Nondeterminism is the absence of this property.
Hmm, that doesn’t seem to exactly how it is used in computation theory, as in famous questions about P != NP.
So if the process is nondeterministic, is it still algorithmic? Or is it nonalgorithmic too?
Comment by orcmid — April 27, 2007 @ 1:57 am
> Hmm, that doesn’t seem to exactly how it is used in computation theory, as in famous questions about P != NP.
This definition corresponds to most descriptions of determinism used when describing automaton that I am aware of. Sometimes a slightly more restricted definition is used, but they are more or less equivalent. Please let me know if you are aware of any direct contradictions or inconsistencies. I am unaware of the P != NP problems involving determinism.
> So if the process is nondeterministic, is it still algorithmic? Or is it nonalgorithmic too?
Depends on your definition of algorithmic ;-)
This is a good question. I say it may be algorithmic. In other words a nondeterministic computation is not neccessarily nonalgorithmic. More on this on my latest post: http://cdiggins.com/2007/04/27/determinism-algorithms-and-wikipedia/
Thanks for your thought provoking comments!
Comment by cdiggins — April 27, 2007 @ 5:54 am
I just grabbed Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979). They define Deterministic one-tape Turing Machines (DTMs) as a fixed model of computation that they use to formalize the notion of algorithm. The class P is essentially the set of polynomial-time DTMs.
They then describe as nondeterministic computations (not algorithms) as ones in which there are choices needing to be made (e.g., the nodes in a route that a traveling salesman will follow), but the choices are made perfectly and it is only necessary to check the result. They use a Non-Deterministic Turing Machine (NDTM) computation model for those.
[My way of describing this is that a nondeterministic computation makes a good (or an optimal) choice at each step and the result is correct (or optimal in some sense). Because the NDTM does not have to find the solution, only check it, it is never slower than the DTM for the same problem and it is often dramatically faster. In particular, the NDTM may provide a result in polynomial time where the DTM might require exponential (non-polynomial) time. (There is always an exponential-time DTM, the question is whether there is always a polynomial-time DTM for every polynomial-time NDTM.)
That is one of the common ways that non-determinism is characterized in computation theory.
I find these exchanges very useful. Wanting to understand what you are doing with Cat is having me look more critically at some things I have not paid much attention to in a very long time.
Comment by orcmid — April 28, 2007 @ 5:26 am