The dark part shows the region where we think finding the sparsest solution to an underdetermined system of linear equations is NP. As time goes, it sure looks like this line is receding. In other words, for every new algorithms shown to work and busting the old limit, the territory of combinatorial problems shrinks and the NP vs P line in the sand shifts.
I cleaned this image up a bit: http://imgur.com/Qs61Q9s
My current research touches CS, so should I find it appropriate to use this concept in an illustration, I'll build it as a svg diagram, and share it here :)
Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from
I would have said: Minor, Minor, who's the sparsest in rank http://en.wikipedia.org/wiki/Minor_%28linear_algebra%29
ReplyDeleteI cleaned this image up a bit: http://imgur.com/Qs61Q9s
ReplyDeleteMy current research touches CS, so should I find it appropriate to use this concept in an illustration, I'll build it as a svg diagram, and share it here :)