How can you prove that a problem is not solvable in a certain time complexity?

Question

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.

Answer 1

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!

Answer 2

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" and Patrascu and Demaine's SICOMP'05 "Logarithmic lower bounds in the cell-probe model" are probably good starting points; look up cell probe lower bounds in Google scholar for much more.

Answer 3

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.