Thesis-related progress
First some background (non-software types may want to skip this post): my thesis project is to form images using a camera without optics, only the raw CCD surface. Naturally, there are limitations to what this kind of sensor can do, but it turns out it can be surprisingly effective. The problem can be found by solving a huge global optimization problem with many local minima.
So, yesterday I determined that a converged solution to the global optimum requires exponential time -- in other words the problem is not computable using the straightforward approach. Not being satisfied with this result, I resolved either to prove my problem is NP-complete or to find a polynomial-time solution. To my happiness, today I came up with a polynomial-time divide-and-conquer solution. I still have to implement and work out the details, but I don't envision any nasty surprises -- and in the worst case I will have a very good approximation algorithm.
So, yesterday I determined that a converged solution to the global optimum requires exponential time -- in other words the problem is not computable using the straightforward approach. Not being satisfied with this result, I resolved either to prove my problem is NP-complete or to find a polynomial-time solution. To my happiness, today I came up with a polynomial-time divide-and-conquer solution. I still have to implement and work out the details, but I don't envision any nasty surprises -- and in the worst case I will have a very good approximation algorithm.