# Polynomial time problems with provably high degree time complexity?

For any integer $k$, does there exist a decision problem in $\textbf P$ that can be proven to require $\Omega(n^k)$ steps?

• Yes. This follows from the time hierarchy theorem. – Yuval Filmus Dec 29 '17 at 22:19
• Is the proof constructive? Can you find a concrete problem for any $k$? – jnalanko Dec 29 '17 at 22:23
• The problem is deciding whether a given Turing machine halts on a given string of length $n$ in time $n^k$. – Yuval Filmus Dec 29 '17 at 22:24
• A more concrete example is, given a graph, to determine whether or not there exists a $k$-clique for a constant $k$. (observe that this is essentially a weaker version of the time-hierarchy theorem) – quicksort Dec 30 '17 at 9:08
• @quicksort I'm pretty sure that the complexity of k-clique is an open poroblem – Ariel Dec 30 '17 at 16:25

The time hierarchy theorem, proved by diagonalization, shows that for every reasonable function $f$ there exists a problem solvable in $O(f(n))$ but not in $o(f(n)/\log f(n))$. One such problem is, given a Turing machine and in input $x$, to determine whether the machine halts in $x$ within $f(|x|)$ steps. In your case, you can choose $f(n) = n^k \log n$ to obtain a problem solvable in $O(n^k \log n)$ but not in $o(n^k)$.