What independence between ZFC and P vs NP would imply

Sup­pose we had a model M that we thought de­scribed can­nons and can­non balls. M con­sists of a set of math­e­mat­i­cal as­ser­tions about can­nons, and the hy­poth­e­sis is that these fully de­scribe can­nons in the sense that any ques­tion about can­nons (“what tra­jec­tory do can­non balls fol­low for cer­tain firing an­gles?”, “Which an­gle should we pick to hit a cer­tain tar­get?”) can be an­swered by de­riv­ing state­ments from M. Sup­pose fur­ther that M is speci­fied in a cer­tain math­e­mat­i­cal sys­tem called A, con­sist­ing of ax­ioms A1...An.

Now there is much to be said about good ways to find out whether M is true of can­nons or not, but con­sider just this par­tic­u­lar (strange) out­come: Sup­pose we dis­cover that a cru­cial ques­tion about can­nons—e.g. Q=”Do can­non balls always land on the ground, for all firing an­gles?”—turned out to be not just un-an­swer­able by our model M but for­mally in­de­pen­dent of the math­e­mat­i­cal sys­tem A in the sense that the ad­di­tion of some ax­iom A0 im­plies Q, while the ad­di­tion of its nega­tion, ~A0, im­plies ~Q.

What would this say about our model for can­nons? Let’s sup­pose that we can take Q as a prima fa­cie sub­stan­tive ques­tion with a defini­tive yes or no an­swer re­gard­less of any model or ax­iom­a­ti­za­tion. At the very least it seems that M must be an in­com­plete model of can­nons if the sys­tem in which it is speci­fied is in­suffi­cient to an­swer the var­i­ous ques­tions of in­ter­est. It seems to me that

If a ques­tion about re­al­ity turns out to be log­i­cally in­de­pen­dent of a model M, then M is not a com­plete model of re­al­ity.

Now we have an ax­iom­a­ti­za­tion of math­e­mat­ics—let’s say it’s ZFC for now—and we have a model of com­pu­ta­tion in re­al­ity, which is M=”The un­vierse can con­tain ma­chines that (effi­ciently) com­pute F iff there ex­ists a Tur­ing ma­chine that (effi­ciently) com­putes F” with ap­pro­pri­ate defi­ni­tions of what ex­actly a Tur­ing ma­chine is in terms of ZFC. Sup­pose we want to an­swer a ques­tion like Q=”Can the uni­verse con­tain ma­chines that effi­ciently solve SAT?”

Un­der the premise that M is true, the ques­tion Q be­comes the pure log­i­cal ques­tion R=”Are there Tur­ing ma­chines that effi­ciently solve SAT?”, i.e. the P ver­sus NP prob­lem.

Now sup­pose that R was shown to be for­mally in­de­pen­dent of ZFC in the sense that for some ax­iom A0, ZFC+A0 im­plies P=NP and ZFC+~A im­plies P!=NP. This would re­solve the math­e­mat­i­cal ques­tion of P ver­sus NP but the ques­tion Q seems like a prima fa­cie con­crete ques­tion with a defini­tive yes or no an­swer that does not rely for its sub­stance on M or ZFC or any other epistemic con­struct. It would seem that we must have missed some­thing in our de­scrip­tion of re­al­ity, M.

Per­haps more con­tro­ver­sially, I claim: Un­der the cor­rect model M’ it seems that it’s im­pos­si­ble for a sub­stan­tive ques­tion (such as Q) to be unan­swer­able.

All this adds up to: The P ver­sus NP prob­lem (and ques­tions like it that can be phrased as defini­tive ques­tions about re­al­ity) must have an an­swer un­less our model of re­al­ity is in­com­plete.