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?

$\endgroup$
10
  • $\begingroup$ Yes. This follows from the time hierarchy theorem. $\endgroup$ Dec 29, 2017 at 22:19
  • $\begingroup$ Is the proof constructive? Can you find a concrete problem for any $k$? $\endgroup$
    – jnalanko
    Dec 29, 2017 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$ Dec 29, 2017 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, 2017 at 9:08
  • $\begingroup$ @quicksort I'm pretty sure that the complexity of k-clique is an open poroblem $\endgroup$
    – Ariel
    Dec 30, 2017 at 16:25

1 Answer 1

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

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