<p>One approach that comes to mind is the work done by Marcus Hutter and Shane Legg on what they call 'Universal Intelligence'. Their <a href="http://www.hutter1.net/" rel="nofollow noreferrer">work</a> 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.</p>

CC BY-SA 4.0
2022-07-28T17:22:46.683Z
2022-07-28T17:22:46.683Z
Mariusmarten
<p>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.</p>
<p>It is open whether learning is hard, i.e. whether there exists an class that is impossible to efficiently (PAC) learn.</p>
<p>Some results that indicate learning is probably hard:</p>
<ol>
<li>Some classes (e.g. automata) are <a href="https://books.google.com/books?id=i3S9_GnHZwYC&amp;pg=PA210" rel="nofollow noreferrer">cryptographically hard</a> to learn.</li>
<li>Some classes (e.g. k-term DNF) are NP-hard to <a href="https://web.archive.org/web/20111110231217/http://www.almaden.ibm.com/cs/people/vitaly/papers/PittValiant88-e.pdf" rel="nofollow noreferrer">properly</a> learn.</li>
</ol>
<p><a href="https://ieeexplore.ieee.org/document/4690955/;jsessionid=4Jsga3a7SVfbv3utVYVEP1IUeFecEG0qezlY9-9vBW9D72pKiDLx!1542376002" rel="nofollow noreferrer">Perhaps some good news?</a>: we're unlikely to find an NP-Hardness of learning result unless the polynomial hierarchy collapses.</p>

CC BY-SA 4.0
2013-01-23T21:48:55.173Z
2022-07-25T09:38:04.810Z
2022-07-25T09:38:04.810Z
Lev Reyzin
<p>What is the computational complexity of computer vision problems (reconstruction, detection, etc.)? Are these problems NP-complete? Are they NP-hard?</p>

<p>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.</p>

<p>Could you also point me to some literature which answers (or tries to answer) this question?</p>

<np-hardness><complexity-classes><machine-learning><cv.computer-vision>
Computational Complexity of Computer Vision Problems
ssb
# Computational Complexity of Computer Vision Problems

(Asked by: username_0 on 2013-01-23)

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?

**Tags:** np-hardness, complexity-classes, machine-learning, cv.computer-vision

---

## 2 answers

### Answer by username_2 on 2013-01-23. Score: 10 | Accepted answer

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](https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA210) to learn.
2. Some classes (e.g. k-term DNF) are NP-hard to [properly](https://web.archive.org/web/20111110231217/http://www.almaden.ibm.com/cs/people/vitaly/papers/PittValiant88-e.pdf) learn.

[Perhaps some good news?](https://ieeexplore.ieee.org/document/4690955/;jsessionid=4Jsga3a7SVfbv3utVYVEP1IUeFecEG0qezlY9-9vBW9D72pKiDLx!1542376002): we're unlikely to find an NP-Hardness of learning result unless the polynomial hierarchy collapses.


---

### Answer by username_1 on 2022-07-28. Score: 1

One approach that comes to mind is the work done by Marcus Hutter and Shane Legg on what they call 'Universal Intelligence'. Their [work](http://www.hutter1.net/) 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.


---

