title: Is the resolution problem in OSGi NP-Complete?
body: <p>The resolution problem is described in the modularity chapter of the OSGi R4 <a href="http://www.osgi.org/Specifications/HomePage" rel="nofollow noreferrer">core specification</a>. It's a constraint satisfaction problem and certainly a challenging  problem to solve efficiently, i.e. not by brute force. The main complications are the uses constraint, which has non-local effects, and the freedom to drop optional imports to obtain a successful resolution.</p>
  
  <p>NP-Completeness is dealt with <a href="https://stackoverflow.com/questions/1857244/np-vs-np-complete-vs-np-hard">elsewhere</a> on StackOverflow.</p>
  
  <p>There has already been plenty of speculation about the answer to this question, so please avoid speculation. Good answers will include a proof or, failing that, a compelling informal argument.</p>
  
  <p>The answer to this question will be valuable to those projects building resolvers for OSGi, including the Eclipse Equinox and Apache Felix open source projects, as well as to the wider OSGi community.</p>