Computational Complexity of Computer Vision Problems
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:


Some classes (e.g. automata) are cryptographically hard to learn.
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.