Article View: comp.lang.prolog
Article #3985Re: Naive Reverse
From: Paul Broome
Date: Mon, 03 Apr 1989 00:48
Date: Mon, 03 Apr 1989 00:48
23 lines
1626 bytes
1626 bytes
In article <193@aucsv.UUCP> ok@aucsv.UUCP (Richard Okeefe) writes: :In article <18765@adm.BRL.MIL>, broome@adm.BRL.MIL (Paul Broome ) writes: :> ... 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. ... :A Prolog program _cannot_ be asymptotically better than the best RAM :algorithms. Sorry, my article was terribly terse and not really about benchmarks. I had in mind using the flexibility of Prolog to explore different algorithms for NP-complete problems. In particular, replacing generate and test methods with those that test (or constrain) while generating. There's an example in CHIP (Constraint Handling in Prolog (Dincbas, LP'88)) where these methods beat existing ones in Fortran. Are there others? Who knows, there might yet be a deterministic polynomial time algorithm for these problems. Failing that, the comparison with existing methods would still be interesting. Paul <broome@brl.mil>
Technical Details
Message-ID:
<18907@adm.BRL.MIL>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!haven!adm!broomeReferences:
<2695@sun.soe.clarkson.edu> <18765@adm.BRL.MIL> <193@aucsv.UUCP>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!haven!adm!broome From: broome@adm.BRL.MIL (Paul Broome ) Newsgroups: comp.lang.prolog Subject: Re: Naive Reverse Summary: Other algorithms for NP-complete problems Message-ID: <18907@adm.BRL.MIL> Date: 3 Apr 89 00:48:56 GMT References: <2695@sun.soe.clarkson.edu> <18765@adm.BRL.MIL> <193@aucsv.UUCP> Reply-To: broome@brl.arpa (Paul Broome (SECAD/CTAB) <broome>) Organization: Ballistic Research Lab (BRL), APG, MD. Lines: 23