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**

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

# What makes a problem computationally NP?

Have something to add?

Draft saved
Draft deleted

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