[dellamonica]

Without digging too much, I don't think such an argument could be made by this paper. A non trivial lower bound on a concrete problem in a general computation framework would be a marvel on its own.

As another example of what I mean, take sorting. There is an omega(n log n) lower bound that applies to a comparison based algorithm, but no lower bound other than trivial n is known for general computation.

It really boils down to how you define your search space. If you encode your input in a way that is already exponential on some parameter n, then even a linear algorithm would take at least exp(n) time just to read the input.

Let's say you have an algorithm, encoded in L characters, that can produce these extremely long paths, then a natural question is whether for any two vectors of n k-bit integers what is the complexity in terms of nk and L of determining whether they are connected? Note that I don't need to generate/read a huge state graph, I could do something smart by understanding the algorithm.