Consider the following reasoning:

Let $K(x)$ denote the Kolmogorov complexity of the string $x$. Chaitin's incompleteness theorem says that

for any consistent and sufficiently strong formal system $S$, there exists a constant $T$ (depending only on the formal system and its language) such that for any strings $x$, $S$ cannot prove that $K(x) \geq T$.

Let $f_n$ be a Boolean function on $n$ variables s.t. the Kolmogorov complexity of its spectrum is at most $k$. Let $S(f_n)$ be the circuit complexity of $f_n$, i.e. the size of the minimal circuit computing $f_n$.

A (rough) upper bound on for $S(f_n)$ is $$S(f_n)\leq c\cdot BB(k) \cdot n$$ for a constant $c$ and $BB(k)$ is a busy beaver function (the maximum possible steps a halting Turing machine with a description of size $k$ can perform). (For every $1$ in the spectrum, construct the minterm of the corresponding truth assignment, and take OR of all these minterms together.)

Suppose now for an infinite family of Boolean functions $L = \{f_n\}_{n}$, we have a formal proof that $L$ requires superlinear size circuits, i.e.

$$S \vdash \forall n \geq n_0, \ g(n)\cdot n \leq S(f_n)$$ where $g(n)\in \omega(1)$.

If we take $n$ to be sufficiently large, we will have $$g(n) > c\cdot BB(T)$$

In particular this would be a proof that the Kolmogorov complexity of the spectrum of $f_n$ is at least $T$, which is impossible.

This leads to two questions:

1) There should be something wrong in the above reasoning. Mainly because it would make superlinear circuit lower bounds formally not provable.

2) Do you know of similar approaches to show barriers for lower bounds, that is, showing that certain types of (circuit) lower bounds are formally unprovable?

  • $\begingroup$ interesting ideas. somewhat related to the razborov/rudich proof re "natural proofs" that does sketch out barriers to P=?NP (but also probably applicable to other complexity class separations as listed as examples in the paper).. have you read that paper? see also barriers P=?NP and barriers/monotone circuit complexity. seeming hints that complexity class separations are similar in structure to unprovability proofs. $\endgroup$
    – vzn
    Jul 20, 2012 at 15:20
  • 2
    $\begingroup$ can you elaborate on "spectrum" of f_n? is there a way to phrase the question without referring to the "spectrum"? $\endgroup$
    – vzn
    Jul 23, 2012 at 3:45
  • $\begingroup$ it is probably true that one can study complexity of functions by studying the smallest TM [in the sense of state table/states] that computes them and that this will roughly match circuit lower bounds. if you can show that it is impossible, rather than really hard, to find that smallest TM, you might have something there. however it is "simple" to find the smallest TM via either canonical enumeration of circuits or TMs. if you ponder why this approach works, it might help to understand why the question does not lead to a problem. $\endgroup$
    – vzn
    Jul 23, 2012 at 3:49
  • 1
    $\begingroup$ Right. Thanks for the references. I know about the Natural Proofs paper. I don't know if the question can be formulated without "spectrum". What I mean by "spectrum" is the sequence $(f(0,0,..,0),f(0,0,..,1),..,f(1,1,..,1))$ $\endgroup$ Jul 23, 2012 at 8:07

2 Answers 2


There is nothing wrong with your argument, but there is no contradiction. You prove that from some large enough $N$ the Kolmogorov complexity of the spectrum of $f_n$ is always at least $T$. But this statement is trivially true! Although we cannot prove that the Kolmogorov complexity of one string is large, if we have a sequence, then from some point it must contain only strings of large complexity. So what is this $N$ that you got? It must satisfy $N>g^{-1}(c \cdot BB(T))$, what is a number that we cannot compute (because of $BB$), so there is no problem at all.

  • $\begingroup$ Thank you. I fell into the trap of believing that one could "choose" some value of N sufficiently large, but as you point out this is not possible within $S$, and as you also correctly point out, this would in fact be true for any family of increasing sequences. $\endgroup$ Jul 23, 2012 at 6:48

Here is an even simpler problematic situation. Let $A(k)$ be the first string (in lexicographic order) such that $K(A(k)) \geq k$; such a string provably exists for all $k$. Then $K(A(k)) \geq k$.

The culprit might be that the formal system cannot compute $BB(T)$.

Edit: Here is a "more explicit" problematic situation. Let $\alpha(k)$ be the maximal length of a string whose Kolmogorov complexity is at most $k$; $\alpha(k)$ provably exists. Then $K(0^{\alpha(k)+1}) > k$.

  • $\begingroup$ Why is this situation problematic? You did not give a program whose output would be A(k) and its length would be less than k. $\endgroup$
    – domotorp
    Jul 20, 2012 at 20:22
  • $\begingroup$ I have the same confusion as Domotor, but I agree that one problem with OP's reasoning is that a formal system will not be able to prove upper bounds on $BB(k)$ for big enough $k$. $\endgroup$ Jul 20, 2012 at 20:53
  • $\begingroup$ It's problematic in (arguably) the same sense as the original question. $\endgroup$ Jul 20, 2012 at 22:01
  • $\begingroup$ I still don't get it. You don't exhibit a string and a proof that its Kolmogorov complexity is large. You exhibit a proof that there exists a string whose complexity is large. $\endgroup$ Jul 21, 2012 at 17:52
  • $\begingroup$ I think that they are problematic in different ways. As I read it, you point to a specific true statement, which does not have a proof. As I lay it out in my question, I point that entails a proof of something which is not provable. $\endgroup$ Jul 22, 2012 at 15:57

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.