NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/sci/logic/2142

Text File | 1992-11-21 | 6.2 KB | 133 lines

Newsgroups: sci.logic
Path: sparky!uunet!psinntp!dorsai.com!mutation
From: [e-mail] (Florian Lengyel)
Subject: Re: Logic and Mathematicians
Message-ID: <[e-mail]>
Organization: The Dorsai Embassy +1.718.729.5018
X-Newsreader: Tin 1.1 PL4
References: <[e-mail]>
Date: Sat, 21 Nov 1992 18:52:05 GMT
Lines: 121

Subject: Re: Logic and Mathematicians
Newsgroups: sci.logic
References: <[e-mail]>
Organization: The Dorsai Embassy +1.718.729.5018
Distribution:
X-Newsreader: Tin 1.1 PL4

[e-mail] (victor yodaiken) writes:
: In article <[e-mail]> [e-mail] (Florian Lengyel) writes:
: >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).
:
: What's the polynomial-time version of Church's thesis?  Note that
: a computation requiring Ackermann(1000,1000)+n steps can be carried out
: in linear time, but is surely not feasably computable.
:
: --
:
:
: [e-mail]
:

The polynomial-time Church-Turing Thesis is that the Turing machine (or
other equivalent models of computation) will not exceed the time and
space requirements of computer computations by more than a polynomial.

In other words, given any computing machine (or equivalent model of
computation) there are constants C and m so that any algorithm that can
be executed on the computing machine in time T(n) and space S(n)
can be executed on a Turing machine in time C * T(n)^m and space C * S(n).


I was referring to the possibility of constructing two models of
ZFC in which P = NP in one, and P <> NP in the other, and was raising
the question whether the models of computation obtained could require
comparable time and space requirements, to within a polynomial.
In other words, I was asking whether an independence proof of P = NP
would violate the polynomial-time Church Turing Thesis.
T(n) = Ackermann(1000,1000)+n is a linear polynomial. If the polynomial
time algorithm for an NP complete-problem in the first model may be
converted to an algorithm in the second model with time complexity
C * T(n)^m and space complexity C * S(n) then the second model would
contain a polynomial time algorithm for an NP-complete problem,
which is a contradiction. So if such an independence proof is
possible, the polynomial-time Church Turing thesis would be violated.

>
> Thanks. That's quite an interesting question. But, it seems implausable
> that any change between models of ZF would change TMs themselves -- since
> they are finite objects. So, a ZF1 proof that P = NP and a ZF2 proof that
> P <> NP would seem to prove a contradiction in ZF itself. That is, the
> same TM T that could compute F in ptime in ZF1 must exist in ZF2, No?
>

Yes, that's exactly what I had in mind. In theoretical computer science
one would like to say that the various notions of computability are
polynomial time equivalent - the polynomial Church-Turing thesis holds.
The reason for this is that theoretical computer scientists want to
convince themselves (and their students)  that the Turing machine (and other
presentations of the computable functions) is a realistic model of
computation: that there is good reason for studying TMs.

I think it is reasonable that in a proposed independence proof of P = NP
given the models ZF1 in which P = NP and ZF2 in which P <> NP, that
both models contain a development of the (partial) computable functions and
their complexity classes. If you believe Chruch's thesis (and I take
your statement about the implausibility of the notion that TM's might change
in different models on account of the finitude of TM's to be an implicit use
of Church's thesis), then the development of the computable functions in either
model will encompass the same class of functions. In particular, polynomials,
hence polynomial time should mean the same thing in both models.

Here I have relaxed the requirement
that the development of the computable functions (or some notion of algorithm)
be identical in both models, which is why I had to invoke the polynomial time
version of Church's thesis. In addition, I wanted to allow for the possibility
that either one of the models might use a notion of computability other
than that of the Turing machine. So in order to avoid the inconsistency
that you mention, one of the models would have to be much more powerful
than the other with regard to computational complexity: the polynomial
time Church Turing thesis would be violated. However, all known
examples of developments of the computable functions as algorithms,
equational calculi, rewriting systems, register machines, recursive functions,
etc, have the same time and space complexity
requirements (that is, an algorithm in one model can be can be simulated
in the other model so that corresponding computations within them have ths
same time and space complexity requirements) to within a polynomial.

Therefore, on the evidence in favor of the Polynomial Time Church's thesis,
if ZFC is consistent, (and meta-mathematics, in which independence proofs
are conducted)  then there is no independence proof of P = NP,
in the sense of exhibiting two  models of ZFC in which P = NP and another
model in which P <> NP.

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.

This does not rule out the possibility that either P = NP is true but
unprovable, or that P <> NP is true but unprovable in ZFC. It is
intended as a statement of meta-meta-mathematics (I conjured this argument
up so that I could use the term) to the effect that a certain
meta-mathematical result (an independence proof) is not possible.

So that is my evidence for believing that the P = NP question will
not have an outcome similiar to that of the continuum hypothesis or
the axiom of choice.






--
[e-mail]
[e-mail]