On the Proof of Non-Existence

I consider the P-NP problem especially difficult because probably P is not equal to P and it is far more difficult to prove that something does not exist than the opposite. I am going to explain why in this article.

Written by Claus Volko
Vienna, Austria, Europe

Contact: cdvolko (at) gmail (dot) com
Homepage: www.cdvolko.net

Let us take the well-known statement "All ravens are black": It is logically equivalent to the statement "There is nothing that is a raven and at the same time not black". This can be expressed in propositional logic as follows:

This is logically equivalent to:

To prove this equivalence, we convert the statement step by step:

We did this by first making use of the fact that every existence proposition for a term A is a negated universal proposition for not-A. Then we make use of the fact that negated conjunction is equivalent with disjunction of negations of propositions. Next we employ the possibility that implications can be expressed as disjunctions and finally that the contraposition of an implication is equivalent to the implication.

This means that we can prove the statement "All ravens are black" if we know all non-black objects and are able to show that none of them is a raven.

In case of the P-NP problem, the statement to be proven is: "There is no NP-complete problem which is an element of P." This could be proven by enumerating all problems in P and showing for each of them that it is not NP-complete. The statement that P is not equal to NP could also be proven by finding a feature all problems in P have which no NP-complete problem has.

However, one should keep in mind that it is not necessary to prove that P is not equal to NP by proving a statement that is logically equivalent to P not being equal to NP. It is also possible to prove that P is not equal to NP by proving a statement that implies P not being equal to NP.

If we take a look at this statement:

It is clear that the following holds:

In the context of the P-NP problem this would mean: If there was not a single NP-complete problem, this would prove that no problem that is in P can be NP-complete. That is trivial and does not help us as we know that there are NP-complete problems.

So we would have to find a true statement which implies what we want to prove. Just considering propositional logic and not features of problems in P as well as NP-complete problems, we will not find such a statement, I think. So we have to investigate what elements of P share apart from the trivial property that they can be solved in polynomial time with regard to the input data.

Claus Volko

This article is a translation of an article from MATHEMATIQ #10.