For any integer $k$, does there exist a decision problem in $\textbf P$ that can be proven to require $\Omega(n^k)$ steps?
1
$\begingroup$
$\endgroup$
-
$\begingroup$ Yes. This follows from the time hierarchy theorem. $\endgroup$ – Yuval Filmus Dec 29 '17 at 22:19
-
$\begingroup$ Is the proof constructive? Can you find a concrete problem for any $k$? $\endgroup$ – jnalanko Dec 29 '17 at 22:23
-
1$\begingroup$ The problem is deciding whether a given Turing machine halts on a given string of length $n$ in time $n^k$. $\endgroup$ – Yuval Filmus Dec 29 '17 at 22:24
-
1$\begingroup$ 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) $\endgroup$ – quicksort Dec 30 '17 at 9:08
-
$\begingroup$ @quicksort I'm pretty sure that the complexity of k-clique is an open poroblem $\endgroup$ – Ariel Dec 30 '17 at 16:25
2
$\begingroup$
$\endgroup$
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)$.
answered Dec 30 '17 at 9:00
