[darcs-users] darcs hang: infinite recursion?

[dagit at eecs.oregonstate.edu]

David Roundy <droundy at darcs.net> writes:

> On Sun, Jun 12, 2005 at 01:06:17PM +0000, Felix Breuer wrote:
>> Hello everyone,
>> 
>> I have stumbled on a problem using darcs that I can neither resolve nor
>> produce a clear bug report for. Can anybody help?
>
> Alas, I *can* help explain the scenario.  What you've run into is the
> infamous O(2^N) behavior of darcs when it encounters certain sorts of
> conflicts.  The code should eventually complete, but it's possible that our
> sun will become a red giant before that happens (which would most likely
> cause darcs to fail).  :(

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 ;)

Thanks,
Jason