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?


2 Answers 2


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.


One approach that comes to mind is the work done by Marcus Hutter and Shane Legg on what they call 'Universal Intelligence'. Their work tries to establish a mathematical foundation for AI and is based on 'Kolmogorov complexity, algorithmic probability, universal Solomonoff induction, Occam's razor, Levin search, sequential decision theory, dynamic programming, reinforcement learning, and rational agents'. They do not make specific statements about any single modality (such as vision) but instead, their Universal Algorithmic Agent (AIXI) considers all possible domains an agent is exposed to.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.