- #1

- 109

- 1

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?

Last edited by a moderator: