3 ms·
No, he means all problems without a (known) polynomial time solution.
by PeCaN 11y ago
No, he means all problems without a (known) polynomial time solution.
- ikeboy 11y agoThat's still not NP, that's NPI+NP-complete.
- lorenzhs 11y agoAs ikeboy implied, NP does not stand for non-polynomial, but for non-deterministic polynomial. Thus the open question whether the two are equal. In particular, it is clear that P is a subset of NP, as any problem that is polynomially computable with a deterministic machine is immediately also polynomially computable with a non-deterministic one by just not using the non-determinism