To produce tangible results in the field of ML/AI, one must take theoretical results under the lens of computational complexity.

Indeed, minimax effectively solves any two-person "board game" with win/loss conditions, but the algorithm quickly becomes untenable for games of large enough size, so it's practically useless asides from toy problems.

In fact, this issue seems to cut at the heart of intelligence itself: the Frame Problem highlights this by observing that any "intelligent" agent that operates under logical axioms must somehow deal with the explosive growth of computational complexity.

So we need to deal with computational complexity: but that doesn't mean researchers must limit themselves with practical concerns. In the past, multilayered perceptrons were thought to be intractable (I think), and thus we couldn't evaluate their utility until recently. I've heard that Bayesian techniques are conceptually elegant, but they become computationally intractable once your dataset becomes large, and thus we usually use variational methods to compute the posterior, instead of naively using the exact solution.

I'm looking for more examples like this: What are examples of "neat" ideas in ML/AI that are impracticable due to computational intractability?

  • 1
    $\begingroup$ Are you also looking for uncomputable algorithms (and not just intractable), but that nonetheless may have approximations? $\endgroup$ – nbro Oct 20 at 23:40
  • $\begingroup$ good question! i didn't consider that. my intent with the question was to see if there are theories/approaches that are hypothesized to produce results, but due to practical concerns (that we have limited compute, that we don't have super-quantum computers, that logic works a certain way, or anything beyond the scope of my imagination) we do not implement / cannot evaluate. i think that has the potential to be overly broad, but for now im just "fishing" for what creative ideas people might say. $\endgroup$ – k.c. sayz 'k.c sayz' Oct 21 at 0:03
  • 1
    $\begingroup$ Ok, then I will add another answer. $\endgroup$ – nbro Oct 21 at 0:07
  • $\begingroup$ but i want something that is at least partially concrete: so something like (im 100% making this up, i dont know what im saying) a function which by definition outputs 1 if insert smart behavior, and then throw said function onto a "thing" that can do unbounded-computation. well... if there's a well-formulated way of defining that i would be curious, but i don't think such a well-formed definition exists..... $\endgroup$ – k.c. sayz 'k.c sayz' Oct 21 at 0:07
  • $\begingroup$ i'm also not interested in the suggestion of "insert universe simulator that knows of all physics" as a function because of above reason. (but if you dear reader can well-formulate this construction, be sure to let me know) $\endgroup$ – k.c. sayz 'k.c sayz' Oct 21 at 0:10

AIXI is a Bayesian, non-Markov, reinforcement learning and artificial general intelligence agent that is incomputable, given the involved incomputable Kolmogorov complexity. However, there are approximations of AIXI, such as AIXItl, described in Universal Artificial Intelligence: Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability (2005), by Marcus Hutter (the original author of AIXI), and MC-AIXI-CTW (which stands for Monte Carlo AIXI Context-Tree Weighting). Here is a Python implementation of MC-AIXI-CTW: https://github.com/gkassel/pyaixi.


To be concrete, exact Bayesian inference is (often) intractable (that is, not polynomially computable) because it involves the computation of an integral over a range of real (or even floating-point) numbers, which is not a polynomial-time operation. More precisely, for example, if you want to find the parameters $\mathbf{\theta} \in \Theta$ of a model given some data $D$, then Bayesian inference is just the application of the Bayes' theorem

\begin{align} p(\mathbf{\theta} \mid D) &= \frac{p(D \mid \mathbf{\theta}) p(\mathbf{\theta})}{p(D)} \\ &= \frac{p(D \mid \mathbf{\theta}) p(\mathbf{\theta})}{\int_{\Theta} p(D \mid \mathbf{\theta}^\prime) p(\mathbf{\theta}^\prime) d \mathbf{\theta}^\prime} \\ &= \frac{p(D \mid \mathbf{\theta}) p(\mathbf{\theta})}{\int_{\Theta} p(D, \mathbf{\theta}^\prime) d \mathbf{\theta}^\prime } \tag{1}\label{1} \end{align}

where $p(\mathbf{\theta} \mid D)$ is the posterior (which is what you want to find or compute), $p(D \mid \mathbf{\theta})$ is the likelihood of your data given the (fixed) parameters $\mathbf{\theta}$, $p(\mathbf{\theta})$ is the prior and $p(D) = \int_{\Theta} p(D \mid \mathbf{\theta}^\prime) p(\mathbf{\theta}^\prime) d \mathbf{\theta}^\prime$ is the evidence of the data (which is an integral given that $\mathbf{\theta}$ is assumed to be a continuous random variable), which is intractable because the integral is over all possible values of $\mathbf{\theta}$, that is, ${\Theta}$. If all terms in \ref{1} were tractable (polynomially computable), then, given more data $D$, you could iteratively keep on updating your posterior (which becomes your prior on the next iteration), and exact Bayesian inference would become tractable.

The variational Bayesian approach casts the problem of inferring $p(\mathbf{\theta} \mid D)$ (which requires the computation of the intractable evidence term) as an optimization problem, which approximately finds the posterior, more precisely, it approximates the intractable posterior, $p(\mathbf{\theta} \mid D)$, with a tractable one, $q(\mathbf{\theta} \mid D)$ (the variational distribution). For example, the important variational auto-encoder (VAEs) paper (which did not introduce the variational Bayesian approach) uses the variational Bayesian approach to approximate a posterior in the context of neural networks (that represent distributions), so that existing machine (or deep) learning techniques (that is, gradient descent with back-propagation) can be used to learn the parameters of a model.

The variational Bayesian approach (VBA) becomes always more appealing in machine learning. For example, Bayesian neural networks (which can partially solve some of the inherent problems of non-Bayesian neural networks) are usually inspired by the results reported in the VAE paper, which shows the feasibility of the VBA in the context of deep learning.

  • 1
    $\begingroup$ @k.c.sayz'k.csayz' Well, I go into the details of Bayesian inference and why they can be intractable (while you don't mention this), so your last edit to your question is fine. I think my answer still addresses some problems related to Bayesian inference that are related to your question. $\endgroup$ – nbro Oct 20 at 23:36
  • 1
    $\begingroup$ Hi @nbro, when you say "which is intractable because the integral is over all possible values of $\theta$", you mean it in a strict complexity theory meaning (i.e. superpolynomial in $\mathcal{D}$) or simply that it is an integral too hard to compute? $\endgroup$ – olinarr Oct 22 at 6:41
  • 1
    $\begingroup$ @olinarr Have a look at this question Intractable posterior distributions, whose answers attempt to address your question. $\endgroup$ – nbro Oct 22 at 12:30
  • 2
    $\begingroup$ @nbro thank you very much. I was just puzzled because, if the input variable is $\mathcal{D}$, then assuming we are doing numerical integration over a pre-determined range of $\theta$s, than shouldn't the computational complexity be constant? (because, independently of $\mathcal{D}$, we always do the same number of "integration steps" over $\theta$). $\endgroup$ – olinarr Oct 22 at 12:39
  • 1
    $\begingroup$ @olinarr I have not found a rigorous argument or proof that shows the time or space complexity of integrals in the case of Bayesian inference. I would also like to see it. Anyway, I think you're right: in terms of complexity theory, the input is $D$ and the integration is over another variable. However, note that the posterior depends on $D$. $\endgroup$ – nbro Oct 22 at 12:44

This question gets at a really interesting fact about AI research in general: AI is hard.

In fact, almost every AI problem is computationally hard (typically NP-Hard, or #P-Hard). This means that most new areas of AI research starts out by characterizing some problem that is intractable, and proposing an algorithm that technically works, but is too slow to be useful. However, that's not the whole story. Usually AI researchers then proceed to develop tractable techniques according to one of two schools:

  • Algorithms that usually work in practice, and are always fast, but are not completely correct.
  • Algorithms that are always correct, and are usually fast, but are sometimes very slow, or only work on specific kinds of sub-problem.

Take together, these let AI address most problems. For example:

  • Search was developed as a general purpose AI technique for solving planning and logic problems. The first algorithm, called the general problem solver, always worked, but was extremely slow. Eventually, we developed heuristic guided search techniques like A*, domain specific tricks like GraphPlan, and stochastic search techniques like Monte-Carlo Tree Search.
  • Bayesian Learning (or Bayesian Inference) has been known since the 1800's, but it is known to involve either the computation of intractable integrals, or the creation of exponentially sized discrete tables, making it NP-Hard. A very simple algorithm involves applying brute force and enumerating all of the options, but this is too slow. Eventually, we developed techniques like Gibbs Sampling (that is always fast, and usually right), or Variable Elimination (that is always right, and usually fast). Today we can solve most problems of this kind very well.
  • Reasoning about language was thought to be very hard (see the Frame Problem), because there are an infinite number of possible sentences, and an infinite number of possible contexts they could be used in. Exact approaches based on rules did not work. Eventually we developed probabilistic approaches like Hidden Markov Models and Deep Neural Networks, that aren't certain to work, but work so well in practice that language problems are, if not completely solve, getting very close.
    • Games of chance, like Poker, were thought to be impossible, because they are #P-Hard to complete exactly (this is harder than NP-Hard). There will probably never be an exact algorithm for these. In spite of this, techniques like CFR+ can derive solutions that are so close to exactly perfect that you would need to play for decades against them to tell the difference.

So, what's still hard?

  • Inferring the structure of a Bayesian network. This is closely related to the problem of causality. It's #P-Hard, but we don't currently have any good algorithms to even do this approximately very well. This is an active area of research.
  • Picking a machine learning algorithm to use for an arbitrary problem. The No Free Lunch theorem tells us this is not possible in general, but it seems like we ought to be able to do it pretty well in practice.
  • More to come...?

The logical induction algorithm can make predictions about whether mathematical statements are true or false, which are eventually consistent; e.g. if A is true, its probability will eventually reach 1; if B implies C then C's probability will eventually reach or exceed B's; the probability of D will eventually be the inverse of not(D); the probabilities of E and F will eventually reach or exceed that of E AND F; etc.

It can also give consistent predictions about itself, e.g. "the logical induction algorithm will predict the probability of X to be Y at timestep T", whilst avoiding paradoxes like the liar's paradox.

  • 1
    $\begingroup$ ohh, this is very cool! MIRI stuff is very hard and i am forced by dumbness to ignore much of their work, but thank you for the source and a short description $\endgroup$ – k.c. sayz 'k.c sayz' Oct 21 at 19:22

In general, partially-observable Markov decision processes (POMDPs) are also computationally intractable to solve exactly. However, there are several approximations methods. See, for example, Value-Function Approximations for Partially Observable Markov Decision Processes (2000) by Milos Hauskrecht.

  • $\begingroup$ wow! so many good answers from you. maybe this question was indeed too broad haha. thank you and i will take some time to digest these hefty papers $\endgroup$ – k.c. sayz 'k.c sayz' Oct 21 at 0:39
  • 1
    $\begingroup$ @k.c.sayz'k.csayz' Well, initially, only AIXI came to my mind, but you were asking for intractable problems, not uncomputable ones. I also thought about providing clarifications and details regarding the intractability of Bayesian inference. Meanwhile, other intractable problems came to my mind, so it is possible that there are other answers to your question :) You're asking for examples, so don't worry, I don't think your question is too broad. $\endgroup$ – nbro Oct 21 at 0:42

Hutter's "fastest and shortest algorithm for all well-defined problems" is the ultimate just-in-time compiler. It runs a given program and, in parallel, searches for proofs that some other program is equivalent but faster. The running program is restarted at exponentially-spaced intervals; if a faster program has been found, that is started instead. The running time of this algorithm is of the same order as the fastest provably-equivalent algorithm, plus a constant $O(1)$ term (the time taken to find the proof, which doesn't dependent on the input size). For example, it will run Bubble Sort in at most $O(n~log (n))$) time, by finding a proof that it's equivalent to such a fast algorithm (like Merge Sort) then switching to that algorithm.

Hutter's algorithm is similar to the best ahead-of-time compilers, known as super-optimisers. They search through all possible programs, starting with the smallest/fastest, until they find one equivalent to the given code. These are actually in use right now, but are only practical for programs that are a few (machine code) instructions long. The LLVM compiler contains some "peephole optimisations" (i.e. find/replace templates) that were found by a super-optimiser a few years ago. Note that super-optimisation should not be confused with super-compilation (a rather general optimisation, which is not optimal and involves no search).


Levin's search algorithm is a general method of function inversion. Many AI tasks are of this sort, e.g. given a cost or reward function (object -> cost or object -> reward), its inverse (cost -> object or reward -> object) would find an object with the given cost/reward; we could ask this inverse function for an object with low cost or high reward.

Levin's algorithm is optimal iff the given function is a "black box" with no known pattern in its output. For example, if a small change in the input produces a small change in the output, Levin search wouldn't be optimal; instead we could use hill climbing or some other gradient method.

Levin's algorithm looks for the function's inverse by running all possible programs in parallel, assigning exponentially more time to shorter programs. Whenever a program halts, we check whether its output is the desired inverse (i.e. whether givenProgram(outputOfHaltedProgram) = desiredOutput, e.g. whether cost(outputOfHaltedProgram) = low).

This way "simpler" guesses at the inverse are made first; where we define the simplicity (AKA "Levin complexity") of a value by looking through all programs $p$ which generate that value, and minimising the sum of: $p$'s length (in bits) plus the logarithm of $p$'s running time (in steps). If we ignored running time we would get Kolmogorov complexity, which is theoretically nicer but is incomputable (we don't know when to give up waiting for short non-halting programs, due to the Halting Problem). Levin complexity is computable, since we can give up waiting for those loops once they've taken exponentially-many steps as a longer solution (e.g. once we've spent $T$ steps waiting for a possible loop of length $N$, we can start trying programs that are $N+1$ bits long for $T/2$ steps).

The running time of Levin Search is of the same order as the simplest such inverse-value-generating program. However, this is misleading, since the fraction of steps allocated to running any particular program $p$ is $1/2^{complexity(p)}$, so this constant factor will be slowing down the computation of the inverse too. There is also overhead associated with context-switching between all of these programs.

The FAST algorithm does the same job as Levin Search, in the same time, but avoids the overhead of context-switching between an infinite number parallel programs. Instead it runs one program at a time, cuts it off if it hasn't halted within an appropriate number of steps, then retries for twice as many steps later on. The GUESS algorithm is also equivalent, but chooses programs at random; the expected runtime is the same, but there's no need to keep track of loop counters like in FAST, plus it can be run on parallel hardware without having to coordinate anything (whilst still avoiding the infinite parallelism of the original).

Levin search is currently impractical in its original setting of searching through general-purpose, Turing-complete programs. It can be useful in less general domains, e.g. searching through the space of hyper-parameters or other domain-specific, configuration-like "programs".

  • 1
    $\begingroup$ Can you specify the time complexity of Levin search, etc.? $\endgroup$ – nbro Oct 22 at 10:20
  • $\begingroup$ Added a bit about time, and "Levin complexity" (which time is parameterised by) $\endgroup$ – Warbo Oct 22 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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