How to prove P$\neq$NP?

Question

I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point.

We can show that P $=$ NP if and only if we can design an algorithm that solves any given instance of problem in NP in polynomial time.

However, I do not understand how on earth can we prove that P$\neq$NP. Please excuse me for the following similitude as it might be so irrelevant, but telling someone to prove if P is not equal to NP appears to me like telling someone to prove that God does not exists.

There is a set of problems, those are unable to be solved by a Non-deterministic Finite Automata (NFA) with polynomial number of states regardless of the current technology (I know this is a sloppy definition). In addition, we have a considerably large set of algorithms which make some crucial problems (shortest path, minimum spanning tree, and even sum of integers ($1 + 2 + \dots + n$) polynomial-time problems.

My question in short: If I believe that P $=$ NP, you would say "then show your algorithm that solves an NP problem in polynomial time!". Suppose that I believe P$\neq$NP. Then what would you exactly ask? What would you want me to show?

The answer is clearly "your proof". However, what kind of proof shows that an algorithm cannot exist? (in this case, a polynomial time algorithm for an NP problem)

Answer 1

There are three main ways I'm aware of that could prove that P$\,\neq\,$NP.

1. Showing that there is some problem that is in NP but not in P. You're probably familiar with the proof that comparison-based sorting need time $\Omega(n\log n)$ to sort a list of $n$ items. One could, in principle, produce a similar proof showing that 3SAT or some other NP-complete problem can't be solved in time $O(n^c)$ for any constant $c$. Geometric Complexity Theory seeks to use tools from algebraic geometry and group representation theory to prove such lower bounds, by considering the symmetries that problems possess. Circuit Complexity is another.

2. Showing that P and NP have different structural properties. For example, P is closed under complementation. If you could show that NP$\,\neq\,$co-NP (i.e., that NP is not closed under complementation), then is must be that P$\,\neq\,$NP. Of course, this is just pushing the problem one level deeper – how would you prove that NP$\,\neq\,$co-NP?

   Another possibility is that we know that NP is exactly the class of problems that can be defined in something called existential second-order logic. If one could show that there's no logic corresponding exactly to P (or if there is a logic but it's different to $\exists\mathrm{SO}$), then P and NP must be different. A related (in fact, equivalent) idea is to show that P doesn't have complete problems under reductions defined by first-order logic, since it's known that NP does have complete problems under these reductions.

3. Prove that some problem isn't NP-complete. If P$\,=\,$NP, then every non-trivial problem in NP is NP-complete under polynomial-time many-one reductions ("non-trivial" here means not $\emptyset$ or $\Sigma^*$). So, if you can show that some problem in NP isn't NP-complete, then we must have P$\,\neq\,$NP.

Answer 2

My question in short: If I believe that P=NP, you would say "then show your algorithm that solves an NP problem in polynomial time!".

Don't forget that you still have to prove that your algorithm solves the problem, and that it runs in polynomial time.

Suppose that I believe P≠NP. Then what would you exactly ask? What would you want me to show?

First, try to explain "why" P≠NP, and why this reason can be used to prove P≠NP in a suitable logical framework. Then sketch a proof, and explain how its most dubious parts can be defended. Next, break down this proof into simpler statements, which can be verified independently.

• For example, the logical framework provided by ZFC is good (even too good in a certain sense) at proving the existence of models (of explicitly given sets of axioms, often even satisfying additional metalogical properties). So if you know a reason for P≠NP related to the existence of a model with some strange properties, then first explain this reason, and then show how the corresponding model can be constructed within ZFC.
• As a non-example, I believe that one reason "why" P≠NP is that mathematics can approximate nearly everything that occurs in the physical world, including randomness. However, it is a known fact that formal systems are very limited in their ability to prove a given string, number, "object", or "artifact" as being essentially random, so it is unlikely that this reason can be used for a proof in any explicitly given deterministic formal system. Maybe if you designed a probabilistic (quantum) proof system were you can verify certain proofs in the system only up to a finite probability depending on your available physical resources ...
• As a likely non-example, the law of the excluded middle basically reflects a static view of the (mathematical) universe, and hence is extremely unlikely to hold in a dynamical universe. Now NP=coNP (or any other collapse of the polynomial hierarchy) would basically be an approximate version of the law of excluded middle with respect to time complexity, but time complexity is too close to a dynamical universe for this to be possible. There are logical frameworks like Girard's linear logic which are able to capture dynamic aspects of the universe, so ... Note however that Brouwer was in a similar situation and already stated the necessary failure of Hilbert's program as fact in his inaugural address Intuitionism and Formalism in 1912 (explaining why it would be circular reasoning), but still was unable to even sketch Gödel's incompleteness proof from 1930.
• As an approximate example, let's try to capture some of the available evidence for P≠NP, namely the exponential lower bound for the traveling salesman polytope, and the intractablilty of resolution based procedures for satisfiability due to weak pigeonhole principles. The "why" in this case is that a certain class of NP-complete problems cannot be solved efficiently by algorithms relying on certain natural (for the class of NP-complete problems considered) principles, like linear programming formulations for TSP, or resolution based proof methods for SAT. Different papers gave different independent reasons why this could be used to prove something, the last paper on TSP for example cited a "close connection between semidefinite programming reformulations of LPs and one-way quantum communication protocols" as reason, while the last paper on resolution cited two independent reasons, namely lower bounds "for a class of formulas representing the pigeonhole principle and for randomly generated formulas".
  You can also observe that there were attempts to strengthen the results over time. The initial results for TSP only concerned symmetric linear programming formulation, while the latest results have no such restriction, and also apply to the maximum cut and maximum stable set problems in addition to TSP. The initial results for resolution considered just basic Davis-Putnam resolution procedures and a single class of artificial counter-examples, while the latest results cover large classes of resolution based methods, and give multiple classes of naturally occurring counter-examples.
  For TSP, I have no idea how the results should be strengthened further, except maybe by applying to more problems in addition to TSP, maximum cut, and maximum stable set. For resolution, I would have many ideas how to strengthen the results further, but the article I linked to is from 2002, Stephen Cook and Phuong Nguyen published a monograph Logical Foundations of Proof Complexity in 2010 which I haven't even browsed, and I guess it will already cover many of my ideas. It is interesting to note how little difference it actually makes to most of us how much these results have been strengthened over time, despite our interest in the P≠NP question. Even if it would have been proven in the meantime that algorithms relying on logical systems without an equivalent of the cut rule cannot efficiently solve satisfiability problems, we would still believe that there has been essentially no progress on P≠NP, that the problem is essentially still as widely open as ever.