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

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

<p>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}) &gt; k$.</p>

CC BY-SA 3.0
2012-07-20T20:22:28.333Z
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.
domotorp
CC BY-SA 3.0
2012-07-20T20:53:22.907Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2012-07-20T22:01:21.040Z
It's problematic in (arguably) the same sense as the original question.
Yuval Filmus
CC BY-SA 3.0
2012-07-21T17:52:49.793Z
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.
Sasho Nikolov
CC BY-SA 3.0
2012-07-22T15:57:28.993Z
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.
Magnus Find
CC BY-SA 3.0
2012-07-20T20:13:10.910Z
2012-07-21T18:33:26.463Z
2012-07-21T18:33:26.463Z
Yuval Filmus
<p>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&gt;g^{-1}(c \cdot BB(T))$, what is a number that we cannot compute (because of $BB$), so there is no problem at all.</p>

CC BY-SA 3.0
2012-07-23T06:48:03.500Z
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.
Magnus Find
CC BY-SA 3.0
2012-07-21T07:52:07.353Z
2012-07-21T07:52:07.353Z
domotorp
<p>Consider the following reasoning:</p>

<p>Let $K(x)$ denote the <a href="https://en.wikipedia.org/wiki/Kolmogorov_complexity">Kolmogorov complexity</a> of the string $x$. 
<a href="https://en.wikipedia.org/wiki/Chaitin%27s_incompleteness_theorem#Chaitin.27s_incompleteness_theorem">Chaitin's incompleteness theorem</a> says that</p>

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

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

<p>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 <a href="https://en.wikipedia.org/wiki/Busy_beaver">busy beaver</a> 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.)</p>

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

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

<p>If we take $n$ to be sufficiently large, we will have
$$g(n) &gt; c\cdot BB(T)$$ </p>

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

<p>This leads to two questions:</p>

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

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

CC BY-SA 3.0
2012-07-20T15:20:58.653Z
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](http://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np) and [barriers/monotone circuit complexity](http://cstheory.stackexchange.com/questions/1484/barriers-and-monotone-circuit-complexity). seeming hints that complexity class separations are similar in structure to unprovability proofs.
vzn
CC BY-SA 3.0
2012-07-23T03:45:33.517Z
can you elaborate on "spectrum" of f_n? is there a way to phrase the question without referring to the "spectrum"?
vzn
CC BY-SA 3.0
2012-07-23T03:49:14.230Z
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.
vzn
CC BY-SA 3.0
2012-07-23T08:07:14.987Z
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))$
Magnus Find
<cc.complexity-theory><reference-request><lo.logic><circuit-complexity><kolmogorov-complexity>
Circuit lower bounds and kolmogorov complexity
Magnus Find
# Circuit lower bounds and kolmogorov complexity

(Asked by: username_0 on 2012-07-20)

Consider the following reasoning:

Let $K(x)$ denote the [Kolmogorov complexity](https://en.wikipedia.org/wiki/Kolmogorov_complexity) of the string $x$.
[Chaitin's incompleteness theorem](https://en.wikipedia.org/wiki/Chaitin%27s_incompleteness_theorem#Chaitin.27s_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](https://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, reference-request, lo.logic, circuit-complexity, kolmogorov-complexity

> **Comments:**
> **username_1**: 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](http://cstheory.stackexchange.com/questions/1388/proofs-barriers-and-p-vs-np) and [barriers/monotone circuit complexity](http://cstheory.stackexchange.com/questions/1484/barriers-and-monotone-circuit-complexity). seeming hints that complexity class separations are similar in structure to unprovability proofs.  
> **username_1**: can you elaborate on "spectrum" of f_n? is there a way to phrase the question without referring to the "spectrum"?  
> **username_1**: 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.  
> **username_0**: 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))$  

---

## 2 answers

### Answer by username_3 on 2012-07-21. Score: 11 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2012-07-20. Score: 1

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$.

> **Comments:**
> **username_3**: 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.  
> **username_4**: 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$.  
> **username_2**: It's problematic in (arguably) the same sense as the original question.  
> **username_4**: 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.  
> **username_0**: 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.  

---

