# Is there a philosophical counterpart question to P != NP?

Gödels motivation to prove his incompleteness theorems was the philosophical statement "This sentence is wrong.". Is there a philosophical counterpart to the statement P != NP? For example such statement might be "This Theorem is practically unprovable". The consequences of an existence of such theorem would be: If the sentence is true, than there is no practical way to prove it. If it is not true, then there is a practical way to prove it, hence it must be true, which is a contradiction. Since P!=NP is such a deep question, I wonder if philosophist have a counterpart question in the sense given above.

• Other than logic, algorithmic compexity is not a philosophical topic. The definitions of P and NP are abstract and, arguably arbitrary; the truth value of "P!=NP" may have little to no effect on the world. Therefore, I don't see how philosophers would care about the statement, at all. But then, I'm not a philosopher. – Raphael Jul 23 '16 at 20:05
• try reading up on razborov/ rudich natural proofs which does fit to some degree such that P vs NP is recast as a question about randomness. also aaronson has a paper on the philosophy of complexity theory. also a good topic for Computer Science Chat – vzn Jul 29 '16 at 4:33
• @vzn the paper you refer to is for 10hours linked below. – Evil Jul 29 '16 at 4:41
• btw 2nd thought godels proof is basically diagonalization which is exactly the same method in the halting problem proof and there is advanced theory that sees the two proofs as nearly identical in structure. so theres your answer :) – vzn Jul 29 '16 at 4:44

Shortly: No.

Gödel motivation was to give closure, in a sense the very same as Hilberts to make one connected field. This is meta-science (meta-mathematics) but not based on philosophy but mathematics.
The concept of truth was connected with logic (in logic it is just well defined symbol), and the idea was to give axiomatic (absolute truth), in order to achieve that the one obvious idea is to give a function (even oracle) that evaluates given object (explicitly loose statement, as it was (and is) underdefined). It was meant to rescue the concept (the truth depends on context, field given, e.g. in Psychology the absolute truth would not be of that much use), which is required to prove anything.

Gödel started as mathematician, the pursuit of closure pushed him to mathematical philosophy (self-studied, not at the professional level), which was used as meta-science, meta-logic, but every time any advancement was made it was back in the field of mathematics. The urge to prove was bigger than to disprove so he picked contraposition to get back to mathematics (CS). After that he succumbed into idealism.

Any proof in given field must be proved in given field, using provided tools, meta-tools and must be verified (and understood) by people from that field otherwise this is just loose statement. In example $P vs NP$ cannot be proved using philosophy, where it is undefined problem. Unfortunatelly it would require to take understanding of the whole field, define the problem using strict notation and use M or CS tools.

The philosophical counterpart does not exist, moreover in that field the $P vs NP$ problem might be defined with assumption of one being true, both or neither. Nothing prevents from defining problem as exclusive alternative or nonexclusive alternative. The concept will be well defined in any cases giving the frame of reference, outcomes and closed entity (world) where we can go further with provided axioms (and this is what we do in CS, there are conditional proofs "if P = NP then ..."). But the task to actually prove it is in the field of Mathematics or Computer Science.

There is no counterpart theory or framework of inference. The sentence you have provided is not proper. Any kind of paradox, tautology or too loose statement to deal with in some other field gives nothing and proves nothing. For the sake of argument if there were counterpart theory it still would be too weak to infer anything. The paradox is something that goes beyond formalism or simply includes mistakes at language level - which are totally irrelevant when analysing in philosophy since it can be resolved at any level giving explicit assumptions.

• Checked with professional philosophist (with academia degree and promoteur, who got his professor title proving Gödel theorem in some alternative way). I anwersed the question since I got insight and the question was not closed. – Evil Jul 28 '16 at 17:02
• What did this philosophist say? – user41014 Jul 28 '16 at 17:10
• What I wrote, made some facts straight about the life of Gödel, showed how mathematical paradox is threated in philosophy, gave long lecture about frame of reference, the required explicit definition and... Essentially turned simple question into two hour talk... I got some paradoxes extra which were called misnomers and fallacies. I gave transcript if relevant parts. I got a request to define $P vs NP$ in understandable and strict sense if I want to get answer. Apart of that Hilbert, ZFC, and the short lecture of defining Mathematics by symbols instead of lexicographic textual description... – Evil Jul 28 '16 at 17:21
• – Evil Jul 28 '16 at 17:41