As the title says, what makes a decision problem NP complex? Is it application of the definition (as in: solvable in polynomial time by a non-deterministic Turing machine)? Also, if P does not equal NP, does it mean that NP problems can only be solved in O(exp(n)) time/steps?(adsbygoogle = window.adsbygoogle || []).push({});

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Featured What makes a problem computationally NP?

Have something to add?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**