# Best known deterministic time complexity lower bound for a natural problem in NP

This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time.

Looking at the comments under answer made me wonder:

Aside from padding and similar tricks, what is the best known time complexity lower bound on a deterministic RAM machine (or multiple-tape deterministic Turing machine) for an interesting problem in NP (which is stated in a natural way)?

Is there any natural problem in NP which is known to be unsolvable in quadratic deterministic time on a reasonable machine model?

Essentially, what I am looking for is an example that rules out the following claim:

any natural NP problem can be solved in $O(n^2)$ time.

Do we know any NP problem similar to those in Karp's 1972 paper or Garey and Johnson 1979 that requires $\Omega(n^2)$ deterministic time? Or is it possible to the best of our knowledge that all interesting natural NP problems can be solved in $O(n^2)$ deterministic time?

### Edit

Clarification to remove any confusion resulting from the mismatch between lower bound and not an upper bound: I am looking for a problem which we know we cannot solve in $o(n^2)$. If a problem satisfies the stronger requirement that $\Omega(n^2)$ or $\omega(n^2)$ time is needed (for all large enough inputs) then better, but infinitely often will do.

• the only superlinear lower bounds I know for natural problems in NP are the time space tradeoffs for SAT (dl.acm.org/citation.cfm?doid=1101821.1101822, and there is follow up work by @RyanWilliams, who will know much more). and they say nothing if the space is allowed to be linear. – Sasho Nikolov May 10 '13 at 16:53
• @SashoNikolov, time-space results are for SAT and there aren't any reductions from many natural NP problems to SAT where the size of the output is linearly bounded in the size of the input. A $\Omega(n^2)$ lower-bound for some natural NP problem need not imply a stronger result for SAT than currently known. – Anonymous May 11 '13 at 3:06
• i am saying i do not know any super linear lower bound for any other natural NP problem – Sasho Nikolov May 11 '13 at 3:22
• How do you use padding to obtain an artificial problem in NP with an $\Omega(n^2)$ time complexity lower bound? – Robin Kothari May 12 '13 at 4:23
• @RobinKothari, take a problem in DTIME($\Omega(2^n)$) and pad it. The proof relies on the nondeterministic time hierarchy theorem and padding was not the right way to refer to the example. We can take an NP problem in NTIME($\Omega(n^2)$) directly. – Anonymous May 12 '13 at 5:22

## 4 Answers

Adachi, Iwata, and Kasai in a 1984 JACM paper show by reduction that the Cat and $k$-Mice game has an $n^{\Omega(k)}$ time lower bound. The problem is in P for each $k$. The problem is played on a directed graph. The moves consist of the cat and then one of the $k$ mice alternating steps. The mice win if they can land on a designated cheese node before the cat lands on them. The question is whether the cat has a forced win. It is actually a complete problem so the lower bound is really based on the diagonalization that gives the time hierarchy.

Grandjean showed that the Pippenger, Paul, Szemeredi, and Trotter time lower bound applies to a SAT encoding, though the result of Santhanam may subsume it.

In addition to the time-space tradeoff lower bounds for SAT mentioned in other comments, there is a body of work on branching program lower bounds which imply time-space tradeoffs for Turing machines. For problems like FFT, sorting or computing universal hash functions there are quadratic tradeoff lower bounds of Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari but these are for functions with many outputs. For decision problems in P, there are time-space tradeoff lower bounds that apply for time bounds that are $O(n \log n)$ but these are weaker than are known for SAT.

• any idea on the relationship of the cat-and-mouse game to NP? – vzn Nov 21 '13 at 17:57

The classic result I know of is due to Paul, Pippenger, Szemeredi and Trotter (1983) and separates deterministic from non-deterministic linear time.

Then, there is the more recent result by Fortnow,Lipton, van Melkebeek and Viglas (2004) that was already mentioned. The uniqueness of this result is that it is a time-space tradeoff result, bounding space as well as time.

However, I am also aware of a result due to Santhanam (2001) that proves a lower bound of $\omega (n \sqrt{ \log ^{*} n} )$. This result is slightly stronger for time contraints than the above, but does not provide any guarantees for space.

Given the above as well as my knowledge of the field, I would say that proving that there is a $\mathbb{NP}$-complete problem that cannot be solved in $O(n^{2})$ deterministic time would be quite a big step. As far as I know, such a result is considered highly nontrivial and likely to require new lower bound techniques.

Note: My wording of the problem in the last paragraph is different than in your question. I could be nit-picky (and perhaps not of much help) and tell you that trivially there is an infinite number of problems in $\mathbb{P}$ and thus in $\mathbb{NP}$ that cannot be solved in $O(n^{2})$ deterministic time, by the deterministic time hierarchy theorem.

Edit: Upon further thinking, here's how you can find a problem in $\mathbb{NP}$ that suits your needs:

1. Any natural problem with a lower bound of $DTIME ( f(n) )$, where $f(n) = \Omega ( n^{2} \log n)$. By the DTIME hierarchy theorem, it requires $\omega( n^{2} )$ time. I believe there exist a handful of these.
2. Any natural problem with a lower bound of $NTIME ( f(n) )$, where $f(n) = \omega ( n^{2} )$, by using the NTIME hierarchy. I am not aware of any such natural problems.
3. Any natural problem with a lower bound of $SPACE ( f(n) )$ , where $f(n) = \omega ( n^{2} / \log n)$. This is justified by the TIME-SPACE separation. I believe that

The above lower bounds should hold for the bit complexity of the problem.

Once again, if you restrict your attention to $\mathbb{NP}$-complete problems, I am not aware of such lower bounds.

• the question asks about a natural problem – Sasho Nikolov May 11 '13 at 2:52
• Thank you but I am not asking about deterministic vs. nondeterministic time: you can take any problem in NTIME($n^k$) as long as it requires $\Omega(n^2)$ deterministic time. Neither the second result answers my question not because it restricts the space but because it is only for SAT, see my reply to Sasho Nikolov below the question. And there are NP-complete problems that cannot be solved in deterministically $\Omega(n^2)$ by padding, I am looking for natural examples. – Anonymous May 11 '13 at 3:13
• @Anonymous are you saying SAT is not a natural problem? – Sasho Nikolov May 11 '13 at 3:42
• @SashoNikolov, SAT is a natural problem. However the result doesn't answer my question positively. Therefore I interpreted it as saying no better answer to my question is known. That doesn't need to be the case. In that sense it doesn't answer my question. – Anonymous May 11 '13 at 4:55
• I will try one last time: while you are right that there is no such implication, I am fairly certain that there is no known unconditional quadratic lower bound against deterministic time for any natural NP problem. It does not follow from the SAT results; it's just the state of affairs – Sasho Nikolov May 11 '13 at 22:22

Perhaps a fairly natural example comes from time-bounded Kolmogorov complexity:

For any fixed $k$, and fixed function $f(n) \leq n$ you can ask: "Given a binary string $x$, does a Turing machine $M$ exist such that $|M| < f(|x|)$ and $M$ produces $x$ in less than $|x|^k$ steps?"

• Thank you, it is not completely artificial but I don't find it a satisfying natural example. – Anonymous May 11 '13 at 3:21
• how do you know that your ramsey problem requires $\Omega(n^k)$ time? – Sasho Nikolov May 11 '13 at 22:26
• @SashoNikolov: I deleted the Ramsey part ... it needs a formal proof :-( – Marzio De Biasi May 12 '13 at 2:54

This is just reasking the same question of P=NP in the a different way, if you can prove that its unsolvable in quadratic time or find an absolute lower bound, you would be proving P!=NP

• Why would a quadratic lower bound for a natural problem in NP show P != NP? – Robin Kothari May 10 '13 at 15:46