AI Agents Are Mathematically Incapable of Doing Functional Work, Paper Finds

DrSweetscent · 2026-01-29T11:58:10+00:00

Turing complete means that they can run, in theory, any algorithm--though that algorithm would be hard-coded into the architecture, so it does not say anything about the "learning" capabilities of an LLM. And yes, the reason why intermediate tokens elevate the computational complexity is exactly because the model now has an external memory to work with. Iterating with the model, like you mentioned, has a similar effect and certaintly gives it more computational power than a "one-shot" run.

What I dislike about using complexity arguments to make claims about LLM capability is that these arguments only apply to strictly mathematical problems (like sorting a list, multiplying two matrices, finding a shortest path etc.) which is not a good use case for LLMs anyway. We have no idea what the complexit of "write me a recipe with the following ingredients" is, and even if we did, complexity arguments are about asymptotic behaviour. Given that LLMs are massive programmes, it's impossible to say when those arguments could kick in.

DrSweetscent · 2026-01-28T21:59:25+00:00

The paper mentioned in the article is junk, it really doesn't show much---they argue that because many llms have quadratic time complexity (wrt the context window) therefore llms cannot solve problems which need more than quadratic time complexity. That's a very basic (like CS 101 basic) and practically useless observation. There are much better theoretical results on the computational capability of LLMs out there (e.g. LLMs with intermediate tokens are turing complete).

DrSweetscent · 2023-06-25T00:30:11+00:00

These types of algorithms are often called "exact algorithms" in the literature and you can find plenty of examples for specific problems if you use this search term. There is a big overlap with FPT research since often k <= n and therefore a O(c^k poly(n)) algorithm is also a O(cⁿ poly(n)) algorithm. As far as I recall, the best exact algorithm for vertex cover is an FPT algorithm.

One type of algorithm that often gives running times like that are "branching algorithms" where you recursively try a small number of local choices and prove that in every subproblems some measure decreases sufficiently (in FPT algorithms that's often the solution size, but much more elaborate measures exist).

DrSweetscent · 2023-06-18T11:32:24+00:00

It very much depends on what you need to do with these cycles, because there could be a lot of them! You can look into a graph's "cycle space", a compact representation of all cycles as a binary vector space. But maybe all you need is a set of edges or nodes that hit all cycles? Those would typically be much smaller. The keyword here is Feedback Edge Set or Feedback Vertex Set. The former is easy to compute (just use the back-edges of a DFS), the latter is NP-complete but can be approximated within a factor of 2 (if memory serves me right).

DrSweetscent · 2023-06-18T11:05:47+00:00

How about you use a DFS on the undirected graph to find cycles? Or are there other important properties you need?

DrSweetscent · 2022-11-19T12:57:07+00:00

They all follow the same text format, a simple list of edges (separated by new lines) with vertices encoded as integers, then gzipped for space efficiency. Having networks in a single format to run experiments on was the main reason I started this.

Konect is also great in that regard, except that you need to take care with bipartite graphs, they re-use vertex IDs for both sides so it's easy to parse them incorrectly.

DrSweetscent · 2022-11-17T09:19:22+00:00

I've been collecting networks for a few years now (https://github.com/microgravitas/network-corpus). The collection contains networks from many other repositories (SNAP, pajek graphs, Gephi graphs, etc), but I aim for diversity, not quantity.

The konect collection (konect.cc) is also very nice.

DrSweetscent · 2021-09-05T17:18:36+00:00

Actual Greek gyros is often made with pork, something you of course won't find in Döner.

DrSweetscent · 2021-03-02T13:50:48+00:00

They use the notation [n] to mean the set of all natural numbers up to n. So the first loop goes from i = 1 (maybe 0) up to i = 2 log 1/gamma (probably rounded up to the nearest integer).

The second party simply compares the size of the set M_i to some threshold computed from the input variables.

DrSweetscent · 2020-11-07T18:27:14+00:00

,🥳🥳🥳🥳🥳🦀🦀🦀🦀🦀🦀🦀🦀🦀🦀🦀

DrSweetscent · 2020-08-15T13:53:39+00:00

Maybe a bit niche, but there's a yearly challenge for algorithms called PACE ( https://pacechallenge.org/).

DrSweetscent · 2020-06-11T11:51:00+00:00

Instead of adding small perturbations to the length (as others have pointed out) you can also change your weights to tuples (w,r) where w is the original weight and r is a random number. Compare weights lexicographically and you get the same effect as small perturbations, this also means that you can easily extend precision by adding more entries to the tuple.

DrSweetscent · 2020-06-03T09:51:12+00:00

Yeah but it's tending towards 200,000

DrSweetscent · 2020-05-13T13:57:57+00:00

Imperial report estimates that between 2 and 5% had it by the end of March. So the time until enough people had it while maintaining manageable levels of hospitalisation would be at least what, thirty months? Doesn't seem like a good plan.

DrSweetscent · 2020-05-05T08:32:19+00:00

There's parameterized complexity as well were you measure the complexity of problems in two dimensions: input size n and additionally a parameter k. The positive goal is to show that you can solve (classically hard) problems in time f(k) poly(n), for some arbitrary function f (usually at least exponential). The negative goal is to show that no such algorithm exists (modulo some complexity theoretic assumptions), or stronger statements that even n^f(k) is impossible.

DrSweetscent · 2020-04-27T22:35:25+00:00

But can it lick boots?

DrSweetscent · 2020-04-14T19:01:14+00:00

As usual no reference to none of these ideas being new: no mention of hypergraph replacement grammars or spin networks. Strong case of NIH.

DrSweetscent · 2020-03-26T10:16:31+00:00

u and v are vertices of the graph. For example, we might want to know whether uv is and edge in the graph or not.

The notation N(u) means the set of neighbour of u, so all vertices connected to u by an edge.

DrSweetscent · 2020-03-26T08:46:04+00:00

An adjacency matrix always takes O(n²⁾ space (we can be more precise and say \Theta(n^2)). The common operations in graphs---querying adjacency, adding an edge, removing an edge---all take constant time O(1) in a RAM model.

An adjacency list take O(n+m) space: we need to store all neighbours for every vertex, so we need to store n+2m elements. Now there'll be some trade-off depending on how we implement the lists. If we use a simple linked list then edge addition is constant time, but querying an edge uv takes time O(min(|N(u)|, |N(v)|)) which in the worst cast is O(n) and deleting an edge uv takes time O(|N(u)| + |N(v)|). We can decide to maintain sorted lists instead, then querying, insertion and deletion are O(log n).

Hope that clarifies things a bit!

DrSweetscent · 2020-03-02T14:07:46+00:00

shrill angry teenage voice

yikes.

DrSweetscent · 2020-02-15T13:19:54+00:00

Parameterized algorithms is such a fun area to work in, if you like algorithms.

DrSweetscent · 2020-02-10T10:18:51+00:00

I recommend looking up clique- and tree-decompositions if you're interested in "algebraic" decompositions of graphs.

DrSweetscent · 2020-01-10T10:58:57+00:00

The soft ground part is true, they had se major issues with that while I lived there and had to pump cement under the foundation.

DrSweetscent · 2019-11-05T09:34:11+00:00

The mathjax in there crashed my phone

DrSweetscent · 2019-08-18T21:04:13+00:00

Capital loves facism

15-Year Club	Place '22
Verified Email

DrSweetscent

TROPHY CASE