3 ms·
A non-deterministic Turing machine has the ability to choose "correctly" from a finite set of options. (This corresponds to search, which gives a nice intuitive
by remexre 5y ago
A non-deterministic Turing machine has the ability to choose "correctly" from a finite set of options. (This corresponds to search, which gives a nice intuitive notion that search can't do better than exponential time without knowledge of the search space unless P=NP.)