Tuesday, February 2, 2010

OSGI Dependency Resolution is NP-Complete

Apparently, the resolution problem in OSGI is NP-Complete, as are similar dependency resolution problems like apt package installation on Debian Linux systems. If you think about it it makes sense, but who would have thought!

I still remember learning about P and NP problems, and the famous P = NP question at university, and being really intrigued by all of it. Lance Fortnow provides an excellent overview of the P = NP problem in Communications of the ACM. It turns out that this is no longer a computer science problem, but one of the fundamental questions in all of science. Fascinating stuff! If only I could find a simple proof :-).

No comments:

Post a Comment