Thursday, September 16, 2010

CS: In this post I continue to not care about any proofs regarding P and NP... and more

I realize that I am commenting on the matter with some lateness .However, irrespective of the expected outcome (see Dick Lipton's latest entry on the subject), one could already make the following statement from day 1: It is very likely we should not care too much about this result in Compressive Sensing as shown in the argument developed here four months ago: In Compressive Sensing: P= NP + Additional Constraints. Let's not even add to that argument that being P also means an algorithm that scale in O(n^501) is OK as opposed to an NP algorithm that scales as O(exp(0.000000001n)).. At our level, the scales and their attendant constants are enormously important, asymptotics are not enough at least when it comes to the reconstruction solvers..

In unrelated news:
Credit: NOAA, NASA

If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

No comments: