What is (Re:) NP-Completeness?
Richard S. Hall
richard.s.hall at oracle.com
Fri Dec 23 07:07:16 PST 2011
On 12/23/11 04:54 , Jaroslav Tulach wrote:
>> ## 23. 12. 2011 09:35:01 ##<
>> First, Richard S. Hall's resolver in Felix has shown that even large
>> systems resolve in a very short time and using very few electrons on the
> I am sure Jesse can modify his simple sample to generate few OSGi bundles and
> make Felix spend all its time resolving dependencies until its computer turns
> into dust.
Given that it is an NP-complete problem, then there is likely no
avoiding the fact that some scenarios will blow it up. I don't think
that's the point.
The Felix 2 resolver was pretty stupid and would blow up occasionally on
scenarios we really saw in the wild. The Felix 3 resolver was rewritten
to be smarter and every scenario we ever discovered in the wild that
caused the Felix 2 resolver to blow up was handled very nicely by the
Felix 3 resolver. This is still the case to my knowledge.
Regardless, it still can blow up. However, if Jesse can modify his
sample to create an reasonably realistic example (i.e., something you
are likely to see in the wild) that blows up the newer Felix resolver,
then we over at Apache Felix would certainly be interested in looking at
it to see if there is a heuristic lurking in there somewhere.
We don't need to solve every scenario, just the ones that actually exist...
More information about the jigsaw-dev