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?EditClarification 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.
Best known deterministic time complexity lower bound for a natural problem in NP
cc.complexity theory;np;p vs np
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.