4 ms·
The "nondeterministic" in NP ("Nondeterministic polynomial") means that problems in NP can be solved in polynomial time by a nondeterministic Turing machine. Su
by readams 3y ago
The "nondeterministic" in NP ("Nondeterministic polynomial") means that problems in NP can be solved in polynomial time by a nondeterministic Turing machine. Such a machine would be like what people incorrectly think quantum computers would be, in the sense that it would explore all the possible paths at once. It's the same meaning as in a nondeterministic finite automaton (NFA) vs a deterministic finite automaton (DFA).
The question of P vs NP is not whether we haven't determined if we can do a particular computation (either at all or in polynomial time). It's whether a deterministic Turing machine could solve in polynomial time the same class of problems that we _know_ a nondeterministic Turing machine could solve in polynomial time.
Of course, the nondeterministic Turing machine is not a physically realistic model of computation.
- btilly 3y agoI'm trying to figure out whether you're just trying to echo what I said in different words, or whether you thought that you were correcting what I said. If the latter, please be specific about what misunderstanding you think I might have.