Is the P vs. NP question formally independent?

Question

This question was considered some years ago by Scott Aaronson http://www.scottaaronson.com/papers/pnp.pdf and after some research I believe the answer is yes. The two main references with the technical details are

• http://epubs.siam.org/doi/abs/10.1137/0204037
• https://ecommons.cornell.edu/handle/1813/6063

There are primitive recursive oracles A and B such that $P^A=NP^A$ and $P^B\ne NP^B$.

There is a p.r. oracle $H^*$ such that $$x\in H^*$$ if and only if $$\bigg(F[\le x](E^*\rightarrow \lnot R^*)\land\lnot F[\le x](E^*\rightarrow R^*)\land x\in A \bigg)\\ \lor \\ \bigg(F[\le x](E^*\rightarrow R^*)\land\lnot F[\le x](E^*\rightarrow \lnot R^*)\land x\in B\bigg)$$ where by definition $$ Q:\leftrightarrow P=NP \\ R^*:\leftrightarrow P^{H^*}=NP^{H^*} \\ E^*:\leftrightarrow (R^*\leftrightarrow Q)$$ and "$F[\le x]S$" denotes the existence of a valid proof with Gödel number not exceeding x for the statement S in the formal system F, which is here understood to be any system containing sufficient arithmetic to acceptably enumerate proofs.

The existence of $H^*$ is provable following Hartmanis and Hopcroft.

$E^*$ is relatively consistent to F: if $F[<\infty]\lnot E^*$ then F itself is inconsistent because it proves its own consistency. Furthermore we can prove that if $F[<\infty]Q$ then $F[<\infty](E^*\rightarrow R^*)$ and if $F[<\infty]\lnot Q$ then $F[<\infty](E^*\rightarrow \lnot R^*)$.

Hence if $F[<\infty]P=NP$ or $F[<\infty]P\ne NP$, then there is a proof of a proof of a contradiction in F.

Related: https://www.schneier.com/blog/archives/2016/11/friday_squid_bl_551.html#c6737756 https://www.schneier.com/blog/archives/2016/09/amtrak_security_1.html#c6735169

EDIT: I have expanded this question into a whole paper, available at the following URLs, and I am still looking for more detailed answers, as my paper lacks a firm conclusion.

• https://www.docdroid.net/OvhoFHI/pnp.pdf.html
• https://drive.google.com/open?id=0B1ahqmM-Tg52ZVVRWVoteTVtTWc

Answer 1

It appears that you are arguing that P=NP is independent of any consistent theory $F$ containing Peano arithmetic. If so, the proof cannot be correct since it would apply to $F=PA + "\!\mathrm{P}=\mathrm{NP}\!"$ (or, for that matter, to $F=PA+ "\!\mathrm{P}\ne \mathrm{NP}\!"),$ so that that P=NP would be independent of those theories too, which clearly isn't true.

If you're really interested in pursuing this, you need to specify in advance the theory that you're trying to prove P=NP independent of (PA, ZFC, whatever). No statement is going to be independent of every theory (or every sufficiently strong theory).