🚀 go-pugleaf

In article <1992Nov21.185205.3566@dorsai.com> mutation@dorsai.com (Florian Lengyel) writes:
>Computing processes seem too fundamental to me, too much a part of the
>way mathematics and meta-mathematics is conducted to begin with ...
>Computing processes, which include the computation of inferences, are  
>absolute, in other words, so they should not be suceptible to varying 
>interpretations of set theory that would lead to such grossly different 
>computational outcomes as P = NP under one interpretation and P <> NP 
>under another.

But non-standard interpretations of ZFC often have non-standard integers.
It is quite possible for an algorithm to "halt" in time n^K, where K is a
non-standard integer in such a model, but not to halt in time n^k for any
actual integer k.

If one could show P=NP in a model of ZFC (or more likely PA) which could be
shown to have non-standard integers, while showing P < NP in a model which
did not appear to require non-standard integers, that would be strong
evidence for P < NP.  Depending on the details, a proof (on the
meta-theoretic level) might even be possible.

It is also possible that P < NP, but that no proof is available in any
system we can accept.  More specifically, P < NP may be independent of ZFC,
but we will not be able to prove it.  This is possible for any unsolved
problem, of course, but it seems more likely for unsolved problems in
complexity theory (and even more so in computability and set theory) than in
most areas.