problems are not decidable in polynomial time is one of the greatest open questions in computer science (see '''P''' versus NP ("P = NP") problem for an in-depth discussion).

An important notion in this context is the set of NP-complete decision problems, which is a subset of NP and might be informally described as the "hardest" problems in NP. If there is a polynomial-time algorithm for even one of them,