3 ms·
As 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,
by lorenzhs 11y ago
As 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