Hacker News new | ask | show | jobs
by SJC_Hacker 797 days 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.
2 comments
eru 796 days 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.

link
keepamovin 797 days ago
That's a good explanation. I didn't know that.
link