On 20050728T221853+0300, Antti-Juhani Kaijanaho wrote: > 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).
Actually, it is better to try to prove that the present problem can be translated in polynomial time into a solution to a known NP-*complete* problem. However, both TSP and SAT are NP-complete. -- 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
