> To add to this NP can also refer to the more formal idea of a non-deterministic turing machine being able to compute the problem in polynomial time. Yes. Thi

> To add to this NP can also refer to the more formal idea of a non-deterministic turing machine being able to compute the problem in polynomial time. Yes. This definition is equivalent to the one about being verifiable in polynomial time, since your non-deterministic TM can just have a different branch for every possible verification "oracle". > I think the more practical definition is "not polynomial"...lol. Well, there are non-polynomial algorithms harder than NP. If a solution can't even be verified efficiently, for example.