6 ms·
I think this what alot of people get wrong. "N' in NP does not stand for "not" it stands for "non-deterministic". Meaning you can solve in P time with a non-de
by SJC_Hacker 3y ago
I think this what alot of people get wrong. "N' in NP does not stand for "not" it stands for "non-deterministic". Meaning you can solve in P time with a non-deterministic Turing machine, or alternatively, a function executing on all inputs in parallel.
So maybe it should really be P and NDP.
- keepamovin 3y agoThat's a good explanation. I didn't know that.
- eru 3y ago> or alternatively, a function executing on all inputs in parallel. I like to explain non-determinism in terms of getting a hint, or having an (untrusted) cheatsheet in a test. Or always making lucky guesses (but you don't trust your guesses). But as long as your parallel executions don't interact at all, the definitions are identical, I think.