Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!ames!ucbcad!ucbvax!basser.cs.su.OZ.AU!ray
From: ray@basser.cs.su.OZ.AU.UUCP
Newsgroups: comp.ai.digest
Subject: Philosophy, Artificial Intelligence and Complexity Theory
Message-ID: <8705251537.AA06291@seismo.CSS.GOV>
Date: Mon, 25-May-87 10:14:46 EDT
Article-I.D.: seismo.8705251537.AA06291
Posted: Mon May 25 10:14:46 1987
Date-Received: Fri, 29-May-87 05:06:25 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Distribution: world
Organization: Dept. of Comp. Science, Uni of Sydney, Australia
Lines: 41
Approved: ailist@stripe.sri.com

Lately I've been chating informally to a philosopher/friend about
common interests in our work.  He was unfamiliar with the concept of the
TIME TO COMPUTE consequences of facts.  Furthermore, the ramifactions of
intractability (ie. if P != NP is, as we all suspect, true) seemed to
be new to my friend.  The absolute consequences are hard to get across
to a non-computer scientist; They always say "but computers are getting
faster all the time...".

I'm digging around for references in AI on these ideas. This isn't my area.
Can anyone suggest some?

I've dug up a couple of relevant papers:

"Some Philosophical Problems from the Standpoint of Artificial Intelligence",
McCarthy and Hayes, 1969.  I think this is the most obvious starting point,
with its description of the frame problem.  However, the authors seem to
discuss the issue from the standpoint of what a formalism must contain so
that the system is CAPABLE of computing what it needs rather than the TIME
to compute these things (please correct me if I'm wrong).  This is  hardly
suprising, as it predates the seminal P=NP? work.

"The Tractability of Subsumption in Frame-Based Description Languages",
Brachman and Levesque, AAAI-84.  This paper is relevant, but too
implementation specific for what I want.  I want something more general
and preferably philosophically oriented.


*NOTE*: I'm certainly NOT implying that AI is impossible! But the notion
of intractability is one that must be addressed.  I'm sure it has been
addressed.  I'm just chasing a few references, more for the benefit of my
colleague than myself.


Raymond Lister
Basser Department of Computer Science
University of Sydney
NSW  2006
AUSTRALIA

ACSnet:  ray@basser
ARPANET: ray%basser.oz@seismo.arpa