News for hackers. Stuff that matters.
Re:What if P = NP? by shasta on Friday April 01, 2011 @02:18PM (#2397363)
Suppose we could resolve (conclusively prove one way or the other) whether P=NP. Then we could also prove that we could resolve whether P=NP. Thus, if we can prove that you cannot prove that you can resolve P=NP, then we have also proven that we cannot resolve P=NP, a contradiction. Thus proving that we cannot prove that we cannot prove that we cannot resolve whether P=NP. This proves that we cannot prove that we cannot prove that we cannot prove that we cannot resolve whether P=NP. etc.
Re:What if P = NP? by vecter on Friday April 01, 2011 @06:30PM (#2398379)
Let A be the statement: "P=NP or P!=NP" (in other words, suppose P vs. NP is decidable in some chosen axiomatic system, like Zermelo-Fraenkel set theory with or without axiom of choice).

You first said:

Suppose we proved A. Then we could also prove that we proved A. This is practically a tautology, since if we proved A, of course we can prove we proved A. I'll just hand you the proof.

Next, you said:

Suppose we can prove ~A (in other words, suppose we can prove that P vs. NP is undecidable in the given axiomatic system). Contradiction!

To sum it up, you said: "Suppose A and ~A. Contradiction!"

Or am I missing something here?

Re:What if P = NP? by shasta on Friday April 01, 2011 @08:02PM (#2398639)
Ya, it looks like I bungled the logic. Let 'Pr X' means 'X is provable'. Let A be your A. Really what I wanted to say is that:

Pr A -> (~Pr ~Pr A)

and thus, Pr a -> Pr ~Pr ~Pr A.

Hence, ~Pr ~Pr ~Pr A -> ~Pr A

Taking A to be ~Pr A, we get:

~Pr ~Pr ~Pr ~Pr A -> ~Pr ~Pr A

So you can peel off pairs of ~Pr until you get down to one or two. Not very surprising, I guess, since Pr A == A in constructive logic, and you can do similar negation collapsing there.