What is (Re:) NP-Completeness?

[Richard S. Hall]

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
>> way.
> 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...

-> richard