Re: Naive Reverse

Article View: comp.lang.prolog

Article #3978

#3978

From: Richard Okeefe
Date: Thu, 30 Mar 1989 06:11

13 lines
1319 bytes

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.)

Technical Details

Message-ID: <193@aucsv.UUCP>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!lll-lcc!lll-winken!uunet!munnari!vuwcomp!dsiramd!marcamd!aucsv!ok

References: <2695@sun.soe.clarkson.edu> <18765@adm.BRL.MIL>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!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

Reply to Parent Message