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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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?"

Answer 4

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