Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!lll-lcc!lll-winken!uunet!munnari!vuwcomp!dsiramd!marcamd!aucsv!ok
From: ok@aucsv.UUCP (Richard Okeefe)
Newsgroups: comp.lang.prolog
Subject: Re: Naive Reverse
Summary: NP-complete is NP-complete
Message-ID: <193@aucsv.UUCP>
Date: 30 Mar 89 06:11:19 GMT
References: <2695@sun.soe.clarkson.edu> <18765@adm.BRL.MIL>
Organization: Computer Science Dept.,University of Auckland,New Zealand
Lines: 13

In article <18765@adm.BRL.MIL>, broome@adm.BRL.MIL (Paul Broome ) writes:
> The naive reverse benchmark is popular because it generates a lot of procedure
> calls.   But it seems that benchmarks for NP-complete problems would be
> most interesting since they require search and search is easy in Prolog.
> Plus we'd be attacking a famous unsolved problem.

It wouldn't be terribly interesting to try NP-complete benchmarks.
NP-complete problems are hard no matter _what_ the programming language.
A Prolog program _cannot_ be asymptotically better than the best RAM
algorithms.  Just because hard problems can be _stated_ easily in a language
doesn't mean they can be _solved_ fast.  (This is not to say that Prolog may
not be an appropriate language for parallel systems, but it can't do any better
than the best parallel algoriothms either.)