Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!husc6!seismo!mcvax!botter!klipper!biep
From: biep@klipper.UUCP
Newsgroups: sci.math,sci.philosophy.tech,comp.ai
Subject: Re: What philosophical problems does complexity theory yield?
Message-ID: <798@klipper.cs.vu.nl>
Date: Wed, 10-Jun-87 04:33:39 EDT
Article-I.D.: klipper.798
Posted: Wed Jun 10 04:33:39 1987
Date-Received: Sun, 14-Jun-87 20:37:54 EDT
References: <789@klipper.cs.vu.nl> <2258@cvl.umd.edu>
Sender: biep@cs.vu.nl
Reply-To: biep@cs.vu.nl (J. A. "Biep" Durieux)
Distribution: world
Organization: VU Informatica, Amsterdam
Lines: 26
Xref: utgpu sci.math:1234 sci.philosophy.tech:171 comp.ai:474
Summary: I see, but...

In article <789@klipper.cs.vu.nl> biep@cs.vu.nl (J. A. "Biep" Durieux) writes:
>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?

In article <2258@cvl.umd.edu> ramesh@cvl.UUCP (Ramesh Sitaraman) writes:
>Yes, you are missing the point !!
>
>The difference between a polynomial and non-polynomial solution for 
>a problem is the difference between structure and a complete lack
>of it.

Thanks a lot, this sounds much more relevant than just computation time.
But, isn't finding the smallest element of a set solvable only by "dumb
exhaustive search" either? Are people having that much trouble with such a
linear algorithm too?

Also, thanks for including the defs! Such things make the net a whole lot
more readable.

But: please don't put your mail address on the "Follow-up-to: " line.
I'm having a terrible time getting this article out!

Inews
feeding
time