How to prove that problem is not in P

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?

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).

StackExchange Computer Science Q#25967, answer score: 15