Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!umnd-cs!umn-cs!moll
From: moll@umn-cs.UUCP
Newsgroups: sci.math,sci.philosophy.tech,comp.ai
Subject: Re: What philosophical problems does complexity theory yield?
Message-ID: <1637@umn-cs.UUCP>
Date: Sat, 6-Jun-87 16:52:53 EDT
Article-I.D.: umn-cs.1637
Posted: Sat Jun  6 16:52:53 1987
Date-Received: Sun, 7-Jun-87 10:07:47 EDT
References: <789@klipper.cs.vu.nl>
Reply-To: moll@umn-cs.UUCP (Rick Moll)
Distribution: world
Organization: University of Minnesota
Lines: 19
Keywords: complexity, hierarchy theorem
Xref: utgpu sci.math:1199 sci.philosophy.tech:153 comp.ai:455
Summary: Infinite hierarchy already known

In article <789@klipper.cs.vu.nl> biep@cs.vu.nl (J. A. "Biep" Durieux) writes:
>Suppose P != NP. Then some things will take a long time to compute.
>But so what?
>As, one by one, all sorts of upper bounds on exponents prove false, and[...]

You seem to be implying that if P=NP then *all* problems can be solved in
polynomial time.  This is certainly not so.  Given any computable function
f(x), one can construct (by diagonalization) a problem which can be solved,
but cannot be solved in time f(n) on a Turing machine.  I believe
the same proof would work for parallel machines. 

>About constant time solutions: Seemingly linear-time solutions can often be
>turned into constant-time solutions by applying parallelism.  [...]

Note that P=NP is stated as a problem about Turing machines (or sometimes
single processor random access machines).  Any problem in the class NP
can definately be solved in polynomial time is one is allowed to use an
arbitrary number (varying with the size of the problem instance) of
processors.