What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard?
In most cases this will boil down to determining the computational complexity of the corresponding machine learning problem. Although generally the machine learning problem is approached statistically rather than combinatorially, I guess this is still pertinent.
Could you also point me to some literature which answers (or tries to answer) this question?