Path: 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) ) Organization: Ballistic Research Lab (BRL), APG, MD. Lines: 23 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