<p>The classic result I know of is due to <a href="http://dl.acm.org/citation.cfm?id=1382850" rel="nofollow">Paul, Pippenger, Szemeredi and Trotter (1983)</a> and separates deterministic from non-deterministic linear time.</p>

<p>Then, there is the more recent result by <a href="http://dl.acm.org/citation.cfm?doid=1101821.1101822" rel="nofollow">Fortnow,Lipton, van Melkebeek and Viglas (2004)</a> that was already mentioned. The uniqueness of this result is that it is a time-space tradeoff result, bounding space as well as time.</p>

<p>However, I am also aware of a result due to <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392" rel="nofollow">Santhanam (2001)</a> 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.</p>

<p>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.</p>

<p>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.</p>

<hr>

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

<ol>
<li>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.</li>
<li>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.</li>
<li>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 </li>
</ol>

<p>The above lower bounds should hold for the bit complexity of the problem.</p>

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

CC BY-SA 3.0
2013-05-11T02:52:31.303Z
the question asks about a natural problem
Sasho Nikolov
CC BY-SA 3.0
2013-05-11T03:13:43.533Z
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
CC BY-SA 3.0
2013-05-11T03:42:50.273Z
@Anonymous are you saying SAT is not a natural problem?
Sasho Nikolov
CC BY-SA 3.0
2013-05-11T04:55:52.103Z
@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
CC BY-SA 3.0
2013-05-11T08:59:43.400Z
I am not sure what you mean by "that does not need to be the case". It *is* the case AFAIK
Sasho Nikolov
CC BY-SA 3.0
2013-05-11T12:31:00.743Z
Actually, I find the question to be of NTIME vs DTIME. I believe you are asking for a result $DTIME( n^{2})  \not \subseteq NTIME( n^{k} ) $, with the added restriction of "natural" problems. The best result I know of this type is Santhanam, without the added restriction. I know that this was the best we knew until 2011 and without having performed an exhaustive search, I haven't heard of such a separation result being published since 2011.
chazisop
CC BY-SA 3.0
2013-05-11T22:15:10.487Z
@SashoNikolov, I don't see how that being the best known lower-bound for SAT implies it is the best known lower-bound for *any* natural NP problem.
Anonymous
CC BY-SA 3.0
2013-05-11T22:18:49.843Z
No, it is not as I don't care about how large the exponent $k$ is. Give me a natural problem that requires $\Omega(n^2)$ nondeterministic time. That would answer the question without any implication for DTIME vs. NTIME. It is straightforward to construct artificial problems in NP that require $\Omega(n^2)$ time. Being natural is not an additional side condition, without it the question is trivial.
Anonymous
CC BY-SA 3.0
2013-05-11T22:22:18.967Z
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
CC BY-SA 3.0
2013-05-27T17:00:10.630Z
@chazisop: Your edit misses the point. According to Sasho Nikolov there is no known quadratic deterministic time lower bound for any natural NP problem.
Anonymous
CC BY-SA 3.0
2013-05-11T01:11:10.663Z
2013-05-20T19:02:38.640Z
2013-05-20T19:02:38.640Z
chazisop
<p>Perhaps a fairly natural example comes <strong>from time-bounded Kolmogorov complexity</strong>:</p>

<p>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| &lt; f(|x|)$ and $M$ produces $x$ in less than $|x|^k$ steps?"</p>

CC BY-SA 3.0
2013-05-11T03:21:43.987Z
Thank you, it is not completely artificial but I don't find it a satisfying natural example.
Anonymous
CC BY-SA 3.0
2013-05-11T22:26:01.947Z
how do you know that your ramsey problem requires $\Omega(n^k)$ time?
Sasho Nikolov
CC BY-SA 3.0
2013-05-12T02:54:23.863Z
@SashoNikolov: I deleted the Ramsey part ... it needs a formal proof :-(
Marzio De Biasi
CC BY-SA 3.0
2013-05-10T18:31:25.403Z
2013-05-12T02:53:46.330Z
2013-05-12T02:53:46.330Z
Marzio De Biasi
<p>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</p>

CC BY-SA 3.0
2013-05-10T15:46:38.390Z
Why would a quadratic lower bound for a natural problem in NP show P != NP?
Robin Kothari
CC BY-SA 3.0
2013-05-10T15:22:11.640Z
2013-05-10T15:22:11.640Z
Alex Gonopolskiy
<p>Adachi, Iwata, and Kasai in a <a href="http://dx.doi.org/10.1145/62.322433">1984 JACM paper</a> 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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-11-21T17:57:10.683Z
any idea on the relationship of the cat-and-mouse game to NP?
vzn
CC BY-SA 3.0
2013-05-13T06:42:38.237Z
2013-05-27T16:49:56.893Z
2013-05-27T16:49:56.893Z
Paul Beame
<p><a href="https://cstheory.stackexchange.com/a/421">This answer</a> to <a href="https://cstheory.stackexchange.com/q/174/">Major unsolved problems in theoretical computer science?</a> question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time.</p>

<p>Looking at the comments under answer made me wonder: </p>

<blockquote>
  <p>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 <em>interesting problem</em> in NP (which is stated in a natural way)?</p>
  
  <p>Is there any natural problem in NP which is known to be unsolvable in quadratic deterministic time on a reasonable machine model?</p>
</blockquote>

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

<blockquote>
  <p>any <em>natural</em> NP problem can be solved in $O(n^2)$ time.</p>
</blockquote>

<p>Do we know any NP problem similar to those in <a href="http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" rel="nofollow noreferrer">Karp's 1972 paper</a> 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?</p>

<h3>Edit</h3>

<p>Clarification to remove any confusion resulting from <a href="https://cstheory.stackexchange.com/questions/5553/what-is-the-right-definition-of-upper-and-lower-bounds">the mismatch between lower bound and not an upper bound</a>: 
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.</p>

CC BY-SA 3.0
2013-05-10T16:53:08.867Z
the only superlinear lower bounds I know for natural problems in NP are the time space tradeoffs for SAT (http://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
CC BY-SA 3.0
2013-05-11T03:06:14.427Z
@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
CC BY-SA 3.0
2013-05-11T03:22:47.640Z
i am saying i do not know any super linear lower bound for any other natural NP problem
Sasho Nikolov
CC BY-SA 3.0
2013-05-12T04:23:00.980Z
How do you use padding to obtain an artificial problem in NP with an $\Omega(n^2)$ time complexity lower bound?
Robin Kothari
CC BY-SA 3.0
2013-05-12T05:22:47.547Z
@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
<cc.complexity-theory><np><p-vs-np>
Best known deterministic time complexity lower bound for a natural problem in NP
Anonymous
# Best known deterministic time complexity lower bound for a natural problem in NP

(Asked by: username_0 on 2013-05-10)

[This answer](https://cstheory.stackexchange.com/a/421) to [Major unsolved problems in theoretical computer science?](https://cstheory.stackexchange.com/q/174/) 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](http://www.cs.berkeley.edu/~luca/cs172/karp.pdf) 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](https://cstheory.stackexchange.com/questions/5553/what-is-the-right-definition-of-upper-and-lower-bounds):
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.

**Tags:** cc.complexity-theory, np, p-vs-np
> **Comments:**
> **username_1**: the only superlinear lower bounds I know for natural problems in NP are the time space tradeoffs for SAT (http://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.  
> **username_0**: @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.  
> **username_1**: i am saying i do not know any super linear lower bound for any other natural NP problem  
> **username_2**: How do you use padding to obtain an artificial problem in NP with an $\Omega(n^2)$ time complexity lower bound?  
> **username_0**: @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.  

---

## 4 answers

### Answer by username_6 on 2013-05-13. Score: 18 | Accepted answer

Adachi, Iwata, and Kasai in a [1984 JACM paper](http://dx.doi.org/10.1145/62.322433) 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.

> **Comments:**
> **username_7**: any idea on the relationship of the cat-and-mouse game to NP?  

---

### Answer by username_3 on 2013-05-11. Score: 13

The classic result I know of is due to [Paul, Pippenger, Szemeredi and Trotter (1983)](http://dl.acm.org/citation.cfm?id=1382850) and separates deterministic from non-deterministic linear time.

Then, there is the more recent result by [Fortnow,Lipton, van Melkebeek and Viglas (2004)](http://dl.acm.org/citation.cfm?doid=1101821.1101822) 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)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392) 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.

> **Comments:**
> **username_1**: the question asks about a natural problem  
> **username_0**: 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.  
> **username_1**: @Anonymous are you saying SAT is not a natural problem?  
> **username_0**: @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.  
> **username_1**: I am not sure what you mean by "that does not need to be the case". It *is* the case AFAIK  
> **username_3**: Actually, I find the question to be of NTIME vs DTIME. I believe you are asking for a result $DTIME( n^{2})  \not \subseteq NTIME( n^{k} ) $, with the added restriction of "natural" problems. The best result I know of this type is Santhanam, without the added restriction. I know that this was the best we knew until 2011 and without having performed an exhaustive search, I haven't heard of such a separation result being published since 2011.  
> **username_0**: @SashoNikolov, I don't see how that being the best known lower-bound for SAT implies it is the best known lower-bound for *any* natural NP problem.  
> **username_0**: No, it is not as I don't care about how large the exponent $k$ is. Give me a natural problem that requires $\Omega(n^2)$ nondeterministic time. That would answer the question without any implication for DTIME vs. NTIME. It is straightforward to construct artificial problems in NP that require $\Omega(n^2)$ time. Being natural is not an additional side condition, without it the question is trivial.  
> **username_1**: 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  
> **username_0**: @chazisop: Your edit misses the point. According to Sasho Nikolov there is no known quadratic deterministic time lower bound for any natural NP problem.  

---

### Answer by username_4 on 2013-05-10. Score: 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?"

> **Comments:**
> **username_0**: Thank you, it is not completely artificial but I don't find it a satisfying natural example.  
> **username_1**: how do you know that your ramsey problem requires $\Omega(n^k)$ time?  
> **username_4**: @SashoNikolov: I deleted the Ramsey part ... it needs a formal proof :-(  

---

### Answer by username_5 on 2013-05-10. Score: -6

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

> **Comments:**
> **username_2**: Why would a quadratic lower bound for a natural problem in NP show P != NP?  

---

