🚀 go-pugleaf

zeleny@husc10.harvard.edu (Michael Zeleny) writes:
: In article <1992Nov15.220359.21971@guinness.idbsu.edu>
: holmes@garnet.idbsu.edu (Randall Holmes) writes:
: 
: >In article <1992Nov14.141234.26280@email.tuwien.ac.at>
: >zach@csdec1.tuwien.ac.at writes:
: 
: >>In article <1992Nov12.204959.17389@husc3.harvard.edu>,
: >>zeleny@husc10.harvard.edu (Michael Zeleny) writes:
: 
: MZ:
: >>>I offer Post's problem as a counterexample.  Also, it doesn't seem
: >>>that there could be a solution for "P =? NP" that would render the
: >>>problem silly in retrospect.
: 
: RZ:
: >>Oh yes: Prove P=NP is independent of ZFC. It actuall HAS
: >>been shown independent in some weak arithmetics.
: 
: Funny, I would have thought independence to be indicative of
: foundational profundity, rather than triviality.
: 
: >>-- 
: >>Richard Zach                         Technische Universitaet Wien
: >>[zach@csdec1.tuwien.ac.at]     Abteilung fuer Formale Logik 185.2
: 
: RH:
: >Wouldn't that actually answer the question?
: 
: Only from the standpoint of a formalist.

Would the construction of two models of ZFC,
  the first, in which P = NP holds
  the second, in which P <> NP holds
call for two models of computation that would violate the polynomial-time
Church's thesis, if not Church's thesis itself?

In the first model, the notion of computation would have an interpretation
which would not be polynomially equivalent to the notion of computation in the
second model. If you believe Church's thesis, the independence proof would
establish that these two notions of computability encompass exactly the
same class of functions. So the encoding of a polynomial time NP-complete 
algorithm in the first model as an algorithm in the second model would not 
be polynomial time.

If you believe the polynomial-time version of Church's thesis, this situation
cannot occur (assuming that polynomial-time means the same thing in both
models). 

A formalist might say: "P = NP is independent of the axioms of set theory,
I cannot derive P = NP or P <> NP from ZFC, therefore the question is
'settled'", but only if the formalist would willfully overlook the
construction of the computable functions and their complexity classes
according to the first and second models, at least one of which would
(it appears to me) involve a non-standard notion of computation.

But I must admit that these possibilities strike me as counterintuitive,
because of my sense that such an independence proof would violate the
polynomial time form of Church's thesis.

: 
: >-- 
: >The opinions expressed		     --Sincerely,
: >above are not the "official"	     M. Randall Holmes
: >opinions of any person		     Math. Dept., Boise State Univ.
: >or institution.			     holmes@opal.idbsu.edu
: 
: cordially,
: mikhail zeleny@husc.harvard.edu
: " -- I shall speak bluntly, because life is short."

Ordinally,

-- 
MUTATION@DORSAI.COM
FLORIAN@NEOTERIC.COM