1
$\begingroup$

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

|cite|improve this question
$\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$

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)$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.