[darcs-users] darcs hang: infinite recursion?
Antti-Juhani Kaijanaho
antti-juhani at kaijanaho.info
Thu Jul 28 19:18:53 UTC 2005
**** 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/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.osuosl.org/pipermail/darcs-users/attachments/20050728/9ecf7057/attachment.pgp
More information about the darcs-users
mailing list