Computational Complexity of Computer Vision Problems

Question

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?

Answer 1

Computer vision is not well defined as a theory problem, but machine learning does have a nice theoretical framework called PAC learning in which one can try to address your question.

It is open whether learning is hard, i.e. whether there exists an class that is impossible to efficiently (PAC) learn.

Some results that indicate learning is probably hard:

1. Some classes (e.g. automata) are cryptographically hard to learn.
2. Some classes (e.g. k-term DNF) are NP-hard to properly learn.

Perhaps some good news?: we're unlikely to find an NP-Hardness of learning result unless the polynomial hierarchy collapses.