<p>All computation is done in a model (simplifying, a model describes the list of instructions allowed), and all computational lower bounds (the smallest amount of instructions required to prove a problem) depend of the model in which they are described. </p>

<ul>
<li><p>Did you mean to say that "<em>there are no problems <strong>in NP</strong> for which it is proven that it cannot be solved in polynomial time</em>"?</p>

<ul>
<li>The statement "<em>there are no problems known for which is proven that it cannot be solved in polynomial time</em>" is just not true (that is, in any computational model I know): see simply the page <a href="http://en.wikipedia.org/wiki/P_(complexity)">http://en.wikipedia.org/wiki/P_(complexity)</a>, section "Relationships to other classes", stating that "P is strictly contained in EXPTIME. Consequently, all EXPTIME-hard problems lie outside P". </li>
</ul></li>
<li><p>As for "<em>problems known for which a proof does exists that it cannot be solved in for example constant or linear time</em>", I give two examples (there are many others!), along with the corresponding computational models:</p>

<ol>
<li><p>In a model where each instruction can query only one element in an array, consider the problem of deciding if an element $x$ is present in an array $A$ of $n$ elements, stored in arbitrary order. No algorithm can decide whether $x$ is present in $A$ in time constant, that is, independent of $n$: this is a problem which cannot be solved in constant time. Such a model is widely used and underlies most programming languages. But in some other (exotic) models (e.g. $x\in\{0,1\}$, $A$ is a bit vector which holds in a memory cell, and the processor can check if all bits of $A$ are zeros or ones in constant time) the problem might be solved in constant time!</p></li>
<li><p>In a model where no instruction permits to use the value of an element in order to compute an index in an array (this is the "Comparison model"), sorting an array of $n$ elements requires at least $\log_2(n!)$ comparisons, which is more than linear (see a complete proof on wikipedia at  <a href="http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list">http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list</a>)</p></li>
</ol></li>
</ul>

<p>I hope it helps!</p>

CC BY-SA 3.0
2013-04-14T09:35:45.217Z
Thank you for your answer, and you're right, I meant to say that there are no problems in NP for which is proven that it cannot be solved in polynomial time. I've updated my question.
Tiddo
CC BY-SA 3.0
2013-04-14T08:40:13.837Z
2013-04-14T08:40:13.837Z
J.y B.y
<p>One area where unconditional and nontrivial time lower bounds are known is in data structures, where the time is for individual data structure operations (or sequences of operations). The standard model for this sort of thing is called the "cell probe model"; it assumes only that main memory is divided into words of a certain size and that the CPU has a very limited amount of local storage (e.g. in registers or cache), and bounds the number of word read/write operations that must be performed.</p>

<p>For instance, in the cell probe model one can prove that the problem of maintaining prefix sums of word-length values (that is, maintain an array of values subject to operations that change one value in an array or that query the sum of a prefix of the values) requires $\Omega(n\log n)$ time to perform a sequence of $n$ operations on an array of length $n$. The difficulty here comes in part from the fact that the operations have to be performed online (not knowing in advance the sequence of future operations).</p>

<p>Fredman and Saks' STOC'89 paper "<a href="http://dl.acm.org/citation.cfm?id=73040">The cell probe complexity of dynamic data structures</a>" and Patrascu and Demaine's SICOMP'05 "<a href="http://arxiv.org/abs/cs.DS/0502041">Logarithmic lower bounds in the cell-probe model</a>" are probably good starting points; look up cell probe lower bounds in Google scholar for much more.</p>

CC BY-SA 3.0
2013-04-15T06:41:31.877Z
Mihai's tutorial from FOCS '10 is great as well: http://techtalks.tv/talks/how-to-grow-your-lower-bounds/1302/.
Sasho Nikolov
CC BY-SA 3.0
2013-04-15T06:17:26.927Z
2013-04-15T06:17:26.927Z
David Eppstein
<p>There are problems for which polynomial time vs exponential time separation is known in the oracle model. For example for the problem of maximizing submodular function subject to cardinality constraint it is known that you cannot get a better than $1-1/e$ approximation algorithm which does polynomial number of value queries. There are several papers which have these kind of lower bounds, but the one which I can remember at the top of my head is <a href="http://arxiv.org/abs/1110.4860" rel="nofollow">http://arxiv.org/abs/1110.4860</a>.</p>

CC BY-SA 3.0
2013-04-17T18:57:38.167Z
2013-04-17T18:57:38.167Z
Ashwinkumar B V
<p>One of the most interesting questions in computer science is of course whether $P = NP$ or $P \neq NP$. If one wants to prove that $P \neq NP$ one can try to prove that an NPC problem is not solvable in polynomial time. However, I can't quite figure out how it would be possible to prove such a thing. </p>

<p>How can you prove that there is no better solution possible to a problem than a solution which has a certain time complexity? </p>

<p>I understand that there are no problems known in NP for which is proven that it cannot be solved in polynomial time, but are there problems known for which a proof does exists that it cannot be solved in for example constant or linear time? Perhaps an example of such a problem can help me understand this better.</p>

<p>EDIT: If you down vote this question could you please at least post a comment why you did so? I'd love to improve my question, but down votes alone don't tell me what I did wrong.</p>

CC BY-SA 3.0
2013-04-14T08:10:11.950Z
I think some people down voted your question because they believe that it is not a research-level question. (see http://cstheory.stackexchange.com/faq and in particular the first two answered questions, "What kind of questions can I ask here?" and "My question is not a research-level question in TCS, where can I ask it?").
J.y B.y
CC BY-SA 3.0
2013-04-14T09:29:30.280Z
@Jeremy - Thank you, you're absolutely right. I should've asked this question on cs.stackexchange.com I guess.
Tiddo
CC BY-SA 3.0
2013-04-14T13:33:31.257Z
See http://en.wikipedia.org/wiki/Time_hierarchy_theorem
András Salamon
CC BY-SA 3.0
2013-04-15T03:57:35.290Z
I strongly oppose closing.  This is not only a research-level question, it is arguably **THE** research-level question!
Jeffε
CC BY-SA 3.0
2013-04-15T06:49:38.937Z
it might be good to focus the question w.r.t. a model of computation. if restricted models (=not polytime equivalent to a multi tape TM) are allowed, then the question might be too broad.
Sasho Nikolov
CC BY-SA 3.0
2013-04-15T15:05:40.703Z
imho, not research level because the question seems not to be aware of the basic time/space hierarchy thms. for example clearly if a problem has a lower bound of space complexity DSPACE(f(n)) then it has time complexity DTIME(f(n)). therefore a problem that requires EXPSPACE requires EXPTIME and an example of this is [Meyer & Stockmeyers proof](http://en.wikipedia.org/wiki/Larry_Stockmeyer): "The equivalence problem for regular expressions with squaring requires exponential space". recommend migrate to cs.se
vzn
CC BY-SA 3.0
2013-04-15T15:45:34.063Z
I'm pretty sure that I should've asked this on cs instead of cstheory. I'm still an undergrad and I just wanted to learn a bit more about complexity theory than the undergrad complexity theory course provided by my university teaches me. Anyway, I got a lot of new information and topics I can dive into from all your replies so it helped me a lot. My apologies for asking this on the wrong stackexchange site.
Tiddo
<cc.complexity-theory><time-complexity><np-complete>
How can you prove that a problem is not solvable in a certain time complexity?
Tiddo
# How can you prove that a problem is not solvable in a certain time complexity?

(Asked by: username_0 on 2013-04-13)

One of the most interesting questions in computer science is of course whether $P = NP$ or $P \neq NP$. If one wants to prove that $P \neq NP$ one can try to prove that an NPC problem is not solvable in polynomial time. However, I can't quite figure out how it would be possible to prove such a thing.

How can you prove that there is no better solution possible to a problem than a solution which has a certain time complexity?

I understand that there are no problems known in NP for which is proven that it cannot be solved in polynomial time, but are there problems known for which a proof does exists that it cannot be solved in for example constant or linear time? Perhaps an example of such a problem can help me understand this better.

EDIT: If you down vote this question could you please at least post a comment why you did so? I'd love to improve my question, but down votes alone don't tell me what I did wrong.

**Tags:** cc.complexity-theory, time-complexity, np-complete

> **Comments:**
> **username_1**: I think some people down voted your question because they believe that it is not a research-level question. (see http://cstheory.stackexchange.com/faq and in particular the first two answered questions, "What kind of questions can I ask here?" and "My question is not a research-level question in TCS, where can I ask it?").  
> **username_0**: @Jeremy - Thank you, you're absolutely right. I should've asked this question on cs.stackexchange.com I guess.  
> **username_2**: See http://en.wikipedia.org/wiki/Time_hierarchy_theorem  
> **username_3**: I strongly oppose closing.  This is not only a research-level question, it is arguably **THE** research-level question!  
> **username_4**: it might be good to focus the question w.r.t. a model of computation. if restricted models (=not polytime equivalent to a multi tape TM) are allowed, then the question might be too broad.  
> **username_5**: imho, not research level because the question seems not to be aware of the basic time/space hierarchy thms. for example clearly if a problem has a lower bound of space complexity DSPACE(f(n)) then it has time complexity DTIME(f(n)). therefore a problem that requires EXPSPACE requires EXPTIME and an example of this is [Meyer & Stockmeyers proof](http://en.wikipedia.org/wiki/Larry_Stockmeyer): "The equivalence problem for regular expressions with squaring requires exponential space". recommend migrate to cs.se  
> **username_0**: I'm pretty sure that I should've asked this on cs instead of cstheory. I'm still an undergrad and I just wanted to learn a bit more about complexity theory than the undergrad complexity theory course provided by my university teaches me. Anyway, I got a lot of new information and topics I can dive into from all your replies so it helped me a lot. My apologies for asking this on the wrong stackexchange site.  

---

## 3 answers

### Answer by username_1 on 2013-04-14. Score: 6 | Accepted answer

All computation is done in a model (simplifying, a model describes the list of instructions allowed), and all computational lower bounds (the smallest amount of instructions required to prove a problem) depend of the model in which they are described.

* Did you mean to say that "*there are no problems **in NP** for which it is proven that it cannot be solved in polynomial time*"?

  + The statement "*there are no problems known for which is proven that it cannot be solved in polynomial time*" is just not true (that is, in any computational model I know): see simply the page <http://en.wikipedia.org/wiki/P_(complexity)>, section "Relationships to other classes", stating that "P is strictly contained in EXPTIME. Consequently, all EXPTIME-hard problems lie outside P".
* As for "*problems known for which a proof does exists that it cannot be solved in for example constant or linear time*", I give two examples (there are many others!), along with the corresponding computational models:

  1. In a model where each instruction can query only one element in an array, consider the problem of deciding if an element $x$ is present in an array $A$ of $n$ elements, stored in arbitrary order. No algorithm can decide whether $x$ is present in $A$ in time constant, that is, independent of $n$: this is a problem which cannot be solved in constant time. Such a model is widely used and underlies most programming languages. But in some other (exotic) models (e.g. $x\in\{0,1\}$, $A$ is a bit vector which holds in a memory cell, and the processor can check if all bits of $A$ are zeros or ones in constant time) the problem might be solved in constant time!
  2. In a model where no instruction permits to use the value of an element in order to compute an index in an array (this is the "Comparison model"), sorting an array of $n$ elements requires at least $\log\_2(n!)$ comparisons, which is more than linear (see a complete proof on wikipedia at <http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list>)

I hope it helps!

> **Comments:**
> **username_0**: Thank you for your answer, and you're right, I meant to say that there are no problems in NP for which is proven that it cannot be solved in polynomial time. I've updated my question.  

---

### Answer by username_6 on 2013-04-15. Score: 14

One area where unconditional and nontrivial time lower bounds are known is in data structures, where the time is for individual data structure operations (or sequences of operations). The standard model for this sort of thing is called the "cell probe model"; it assumes only that main memory is divided into words of a certain size and that the CPU has a very limited amount of local storage (e.g. in registers or cache), and bounds the number of word read/write operations that must be performed.

For instance, in the cell probe model one can prove that the problem of maintaining prefix sums of word-length values (that is, maintain an array of values subject to operations that change one value in an array or that query the sum of a prefix of the values) requires $\Omega(n\log n)$ time to perform a sequence of $n$ operations on an array of length $n$. The difficulty here comes in part from the fact that the operations have to be performed online (not knowing in advance the sequence of future operations).

Fredman and Saks' STOC'89 paper "[The cell probe complexity of dynamic data structures](http://dl.acm.org/citation.cfm?id=73040)" and Patrascu and Demaine's SICOMP'05 "[Logarithmic lower bounds in the cell-probe model](http://arxiv.org/abs/cs.DS/0502041)" are probably good starting points; look up cell probe lower bounds in Google scholar for much more.

> **Comments:**
> **username_4**: Mihai's tutorial from FOCS '10 is great as well: http://techtalks.tv/talks/how-to-grow-your-lower-bounds/1302/.  

---

### Answer by username_7 on 2013-04-17. Score: 4

There are problems for which polynomial time vs exponential time separation is known in the oracle model. For example for the problem of maximizing submodular function subject to cardinality constraint it is known that you cannot get a better than $1-1/e$ approximation algorithm which does polynomial number of value queries. There are several papers which have these kind of lower bounds, but the one which I can remember at the top of my head is <http://arxiv.org/abs/1110.4860>.


---

