Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!husc6!seismo!decuac!cvl!ramesh
From: ramesh@cvl.UUCP
Newsgroups: sci.math,sci.philosophy.tech,comp.ai
Subject: Re: What philosophical problems does complexity theory yield?
Message-ID: <2258@cvl.umd.edu>
Date: Thu, 4-Jun-87 12:09:44 EDT
Article-I.D.: cvl.2258
Posted: Thu Jun  4 12:09:44 1987
Date-Received: Sat, 6-Jun-87 06:58:39 EDT
References: <789@klipper.cs.vu.nl>
Reply-To: ramesh@cvl.UUCP (Ramesh Sitaraman)
Followup-To: ramesh@cvl.umd.edu
Distribution: world
Organization: Center for Automation Research, Univ. of Md.
Lines: 34
Xref: utgpu sci.math:1182 sci.philosophy.tech:141 comp.ai:449

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? (Shouldn't I have asked that at the
>beginning of this article? :-))
>-- 

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. If P not = NP we would have shown that some problems can be 
solved only by something similar to a dumb exhaustive search over
the solution space i.e. there is not enough structure in the 
problem to constrain its solutions.

Graph theorists have found eulerian circuits very interesting 
and there have been very strong theorems proved about graphs
with this property. However, the seemingly similar problem 
of Hamiltonian circuits have almost no characterisation inspite
of dilligent efforts for the past 100 years or so. The theory of
NP-completeness explains this anomaly. Eulerian circuit can be
solved in linear time while Hamiltonian circuit is NP-complete !!!

				Ramesh

(Defn:
      Eulerian ckt: A circuit passing through all edges of a graph
	without repeating an edge.
      Hamiltonian ckt: A circuit passing through all the vertices
	of a graph without repeating a vertex.
)