Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!seismo!mcvax!botter!klipper!biep
From: biep@klipper.UUCP
Newsgroups: sci.math,sci.philosophy.tech,comp.ai
Subject: What philosophical problems does complexity theory yield?
Message-ID: <789@klipper.cs.vu.nl>
Date: Wed, 3-Jun-87 13:15:21 EDT
Article-I.D.: klipper.789
Posted: Wed Jun  3 13:15:21 1987
Date-Received: Sat, 6-Jun-87 06:24:50 EDT
Reply-To: biep@cs.vu.nl (J. A. "Biep" Durieux)
Distribution: world
Organization: VU Informatica, Amsterdam
Lines: 31
Xref: utgpu sci.math:1180 sci.philosophy.tech:137 comp.ai:448

Suppose P != NP. Then some things will take a long time to compute.
But so what?

Suppose someone finds out not all problems can be solved in constant
time. Now that comes as a philosophical shock, of course. That has
lots of implications.

But once one has overcome that shock, finding that some problems cannot
be solved in linear time may be annoying, but now since the possibility
of constant time already has been destroyed, it's no great news.

As, one by one, all sorts of upper bounds on exponents prove false, and
finally it seems polynomial time isn't good at all, one gets even bored
by all those variations on the same theme, not? So what exactly is so
exciting about that polynomial limit?


About constant time solutions: Seemingly linear-time solutions can often be
turned into constant-time solutions by applying parallelism. This is the
way the universe is able to simulate itself, however big it (object) may
be or grow. I don't know of what complexity the collapsing of a wave-
function would be supposed that all "time-space-points" of it worked
parallelly on it.
But, isn't anything which cannot be turned into a constant-time process
philosophically annoying? Why just hassling about non-polynomial time
solutions? Am I missing something? (Shouldn't I have asked that at the
beginning of this article? :-))
-- 
						Biep.  (biep@cs.vu.nl via mcvax)
Popper tells us how science ought to be done - Kuhn tells us how it *is* done.
	And I ... I read neither.