2nd-Order P-NP Problem

In this short essay, I introduce my own approach to the P-NP problem. I argue why it might actually be the case that the P-NP problem is unsolvable, that is: P is probably not equal to NP, yet it will not be possible to ever find a mathematical proof for this.

Written by Claus Volko
Vienna, Austria, Europe

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

The P-NP problem has been subject of debate for decades. Most scholars believe that the answer to the question whether P is equal to NP is no; but nobody has managed to prove this hypothesis. This raises the question whether the P-NP problem is solvable at all. I would like to introduce what I call the Second-Order P-NP problem: Is it possible to prove that P is not equal to NP?

If P were equal to NP, the answer would be no. Alas, if P is not equal to NP, the answer is probably no as well; for it is infinitely more difficult to show that no algorithm with polynomial runtime exists for any NP-complete problem than to find such an algorithm (if it exists). The Second-Order PNP problem is related to the Halting problem: We can easily detect that an algorithm terminates (i. e. it finds a polynomial algorithm for an NP-complete problem), but we can by no means prove that an algorithm will never terminate (i. e. no polynomial algorithm for any NP-complete problem can be found). The answer to the Second-Order P-NP problem is only yes if a proof for P not equal NP can be easily found. Unless P is equal to NP, the P-NP problem can only be solved if the answer to the Second-Order P-NP problem is yes.

Now if we take a look at Higher-Order P-NP problems, following analogous definitions, we will observe an infinite regression. It seems that it is neither provable that P is not equal to NP, nor that the statement that it is not provable that P is not equal to NP is provable, nor...

All in all, this gives very little hope that the P-NP problem will ever be solved.

This article was first published on my personal homepage in 2015.

Claus Volko