Now suppose that R was shown to be formally independent of ZFC in the sense that for some axiom A0, ZFC+A0 implies P=NP and ZFC+~A implies P!=NP. This would resolve the mathematical question of P versus NP
This is only true if A0 is independent of ZFC. This makes things unnecessarily complicated and obscures how one would usually prove that something is independent. There are a variety of methods of showing that something is independent, but the most common method is to construct two models of the theory, one with the statement and the other with the negation. If both models are contained in your original system then you know that as long as your original system is consistent, your desired statement is independent. A more concrete example that avoids a lot of the subtleties and abstractions is what happened with the parallel postulate in the 19th century. By making slightly other geometries (such as geometries on the surface of a sphere), one could do the exact same process as above.
All this adds up to: The P versus NP problem (and questions like it that can be phrased as definitive questions about reality) must have an answer unless our model of reality is incomplete
I think you may be confusing reality with our models here. Consider for example the possibility that our universe is actually discrete and finite. If that’s the case, then a decent model won’t answer whether P != NP or not in the abstract sense.
In general, when a specific question is being asked it helps to try to put in the less abstract version and see if anything changes. In this context, what do you think happens if we replace P ! = NP with some more concrete question? Say for example I want to know if 3^^^^^^3 + 1 has an even or odd number of prime factors. This is at least more concrete in that you can specify a specific computation that if you could do it you could then answer this question. I don’t know of any easy way to answer this sort of question but it looks really difficult. It may well be that this question is simply unresolvable in our universe because the computational resources to answer it don’t exist. But from the perspective of something like ZFC this question is trivial. This suggests to me that there are subtle issues going on here that you aren’t quite addressing. P != NP is a particularly tricky question because there are so many options for what could happen that are logically consistent but seem weird (e.g. there’s an algorithm that solves 3-SAT in polynomial time but this can’t be proven in ZFC. Or the algorithm’s correctness can be proven but not a polynomial bound on its run time. Or the run time can be proven but not the correctness of the algorithm. Etc.)
How issues like undecidability and our modeling of reality interact are really tough. It isn’t helpful to jump in with them using an example that is itself really abstract.
I think you may be confusing reality with our models here.
Yeah my claim was a little ambiguous. I meant to claim that either (1) our current model of reality fails to describe some truths about the universe or (2) P=NP is decidable in our model. [I’m only clarifying the claim, I’m now dubious about whether this it is true.] You’re right- I should add (3) P=NP cannot be cast as a question about reality.
This is only true if A0 is independent of ZFC. This makes things unnecessarily complicated and obscures how one would usually prove that something is independent. There are a variety of methods of showing that something is independent, but the most common method is to construct two models of the theory, one with the statement and the other with the negation. If both models are contained in your original system then you know that as long as your original system is consistent, your desired statement is independent. A more concrete example that avoids a lot of the subtleties and abstractions is what happened with the parallel postulate in the 19th century. By making slightly other geometries (such as geometries on the surface of a sphere), one could do the exact same process as above.
I think you may be confusing reality with our models here. Consider for example the possibility that our universe is actually discrete and finite. If that’s the case, then a decent model won’t answer whether P != NP or not in the abstract sense.
In general, when a specific question is being asked it helps to try to put in the less abstract version and see if anything changes. In this context, what do you think happens if we replace P ! = NP with some more concrete question? Say for example I want to know if 3^^^^^^3 + 1 has an even or odd number of prime factors. This is at least more concrete in that you can specify a specific computation that if you could do it you could then answer this question. I don’t know of any easy way to answer this sort of question but it looks really difficult. It may well be that this question is simply unresolvable in our universe because the computational resources to answer it don’t exist. But from the perspective of something like ZFC this question is trivial. This suggests to me that there are subtle issues going on here that you aren’t quite addressing. P != NP is a particularly tricky question because there are so many options for what could happen that are logically consistent but seem weird (e.g. there’s an algorithm that solves 3-SAT in polynomial time but this can’t be proven in ZFC. Or the algorithm’s correctness can be proven but not a polynomial bound on its run time. Or the run time can be proven but not the correctness of the algorithm. Etc.)
How issues like undecidability and our modeling of reality interact are really tough. It isn’t helpful to jump in with them using an example that is itself really abstract.
All of that said, there’s an overview by Scott Aaronson on whether P != NP is undecidable that is worth reading(pdf). He does also discuss towards the end some of the issues you are touching on.
Yeah my claim was a little ambiguous. I meant to claim that either (1) our current model of reality fails to describe some truths about the universe or (2) P=NP is decidable in our model. [I’m only clarifying the claim, I’m now dubious about whether this it is true.] You’re right- I should add (3) P=NP cannot be cast as a question about reality.