On Thursday 27 April 2006 21:53, Ralf Treinen wrote: > The constraint solving algorithm is complete, that is it finds a > solution whenever there exists one, even for multiple disjunctive > dependencies and deep package conflicts. This problem is computationally > intractable in theory (that is, NP-complete), but can in practice be > solved very efficiently.
Can you elaborate? I can see 3 possibilities: * P = NP and upstream found this and sits on the result * The (NP complete) problem the tool claims to solve is not the exact problem the tool solves in reality, thus the tool solves a different problem. * The problem is NP complete but this is not relevant yet, with only a few 10000 thousand packages. Try with a few 100000 packages and be prepared to wait hours and/or invest in a few TB main memory... ;-) I guess it's the second, or perhaps the thirs. cheers -- vbi -- If this fortune didn't exist, somebody would have invented it.
pgpP9LPfo1J6g.pgp
Description: PGP signature
