**** Warning: computer science follows :) **** On 20050728T081750-0400, David Roundy wrote: > Jason wrote: > > David, have you ever checked if you're solving an NP-Complete problem > > with your conflict code? I'm hoping the answer is that someone has > > checked and that this problem should indeed have a polynomial time > > algorithm, but I thought I'd ask anyway ;) > > No, I don't know how one would check.
Actually, the more interesting question is whether it is NP-hard :) A standard proof of NP-hardness consists of proving that any solution to the present problem can be translated in polynomial time into a solution to a known NP-hard problem. Famous known NP-hard problems include the travelling salesman problem (find the cheapest path that visits all of the given nodes of a complete weighted graph, and none of them twice) and the SAT problem (determine if a propositional sentence is satisfiable). *** What is the difference between NP-hard and NP-complete? The set of NP-hard problems can be informally characterized as the set of problems that, according to current knowledge, cannot have an efficient solution. The set of NP-complete problems is a subset of that set; it excludes those problems that are not _nondeterministically polynomial_ aka NP, ie. those problems whose solutions cannot be recognized in polynomial time. For most practical purposes, NP-hard is the interesting set. However, if the open problem of P=NP is solved and the answer turns out to be affirmative, then NP-complete problems do have a polynomial solution. In essence, NP-complete problems look hard now but might - if we are extremely lucky - actually be easy, while those NP-hard problems that are not NP-complete will always be hard. -- Antti-Juhani Kaijanaho http://antti-juhani.kaijanaho.info/ Blogi - http://kaijanaho.info/antti-juhani/blog/ Toys - http://www.cc.jyu.fi/yhd/toys/
signature.asc
Description: Digital signature
_______________________________________________ darcs-users mailing list [email protected] http://www.abridgegame.org/mailman/listinfo/darcs-users
