How to prove that problem is not in P

Question

Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis?

Answer 1

The most common technique is to prove that the problem is hard for some class. For example, consider the problem HALT in which we are given a Turing machine $T$ and a number $n$ (encoded in binary, i.e., in the usual way), and the task is to decide whether $T$ halts within $n$ steps. HALT is EXPTIME-hard. If HALT were in P then P=EXPTIME (using the EXPTIME-hardness of HALT), which contradicts the time hierarchy theorem. We conclude that HALT is not in P.

Consider now a different problem, REGEXP-INT, in which given a list of regular expressions, we have to decide whether their intersection is empty. This problem is coPSPACE-hard, and so if it were in P, then P=PSPACE. While we don't know for sure that P is different from PSPACE, this is widely conjectured (and follows from P$\neq$NP), and assuming that, we conclude that REGEXP-INT is not in P. We call this a conditional result. Similarly, SAT is NP-hard, and so unless P=NP, SAT is not in P.

The unconditional results invariably use one of the hierarchy theorems, and so eventually, diagonalization. This technique itself cannot separate P from NP, due to the so-called "relativization" barrier (though non-black-box diagonalization still stands a chance).

Answer 2

The generally easiest solution for this kind of thing is to assume that you can do it, and show that it contradicts a well-established result.

The easiest case will be when you can show that the problem is undecidable -- not in P, not in NP, not guaranteed to halt, ever. Those solutions typically read like:

"Suppose, for contradiction, that there exists an algorithm for the Foo problem. I will show you that if I was able to solve the Foo problem at all, then I would be able to decide if any arbitrary program halted, since I can somehow reduce the question of "Does algorithm Bar halt on input $s$?" to an instance of the Foo problem. The halting problem is undecidable, a contradiction. Hence no such algorithm exists, in particular, no algorithm in P."

Your next best bet would be to show that it would give you a polynomial time solution to something in EXPTIME, and P $\subsetneq$ EXPTIME. That would look like this:

"Suppose, for contradiction, that there exists an $O(n^c)$-time algorithm for the Foo problem, where $c$ is a constant. I will show you that, in no more than polynomial time, I can reduce some existing problem known to be in EXPTIME but not in P to an instance of the Foo problem, a contradiction. Hence no such algorithm exists."

Anything other than that is hard. We haven't proved very many results about the limits of P.

Answer 3

Showing a lower bound on a problem is much harder than showing an upper bound. For an upper bound you simply must show an example algorithm of that complexity (a witness). Conversely, for the lower bound you have show that for all solutions each takes at least $\Omega(f(N))$ steps where $f(N)$ is some super-polynomial function. One simple case is where the output is exponential in the input.

• The Towers of Hanoi is an example problem where one can prove a lower bound (of exponential time) in any solution. The gist of the proof is to show that any algorithm must generate each of the $\Omega(2^N)$ positions.

Another example (but one in $P$).

• Any comparison-based sort is $\Omega(N \log N)$.

Answer 4

of course the big open question is P=?NP as commenters have noticed but you dont specifically mention NP. what neophytes not realize is that there are many problems proven outside of P, its just than none are NP-complete. it is possible to prove a problem takes more than P time ie is "not in P" if it takes eg ExpTime. the simplest way to prove a problem requires ExpTime is to prove it requires ExpSpace. this has been done with a sophisticated problem involving regular languages:

• Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

the proof involves showing that any TM that computes a language using Expspace can be computed by the above problem/formulation. so proving that any problem reduces to this ExpSpace complete problem in the above paper is sufficient.