<p>Let $f$ be a boolean function over $n$ variables $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}$. We are looking now for a representation of $f$ s.t. when given that representation and values $x_1, \ldots, x_n$, a turing machine in $PH$ can decide whether $f(x_1, \ldots, x_n) = 1$.</p>

<blockquote>
  <p>What is the smallest representation of a boolean function meeting these requirements?</p>
</blockquote>

<p>Circuits seem an intuitive choice, and a turing machine in $P$ can decide whether a set of values $x_1, \ldots, x_n$ satisfies that function. But circuits take upto exponential size in $n$, so we're hoping on smaller representations, given that the complexity of the machine calculating the result of the function can be much higher.</p>

<p>There are no bounds on the complexity of the function computing the representation.</p>

CC BY-SA 3.0
2011-10-29T10:50:43.427Z
Isn't the trivial answer a binary string of length $2^n$? Unless you know something about your $f$, you cannot have anything smaller.
Jukka Suomela
CC BY-SA 3.0
2011-10-30T20:59:48.247Z
You're probably looking for the resource-bounded Kolmogorov complexity of the truth table of $f$.
Mahdi Cheraghchi
CC BY-SA 3.0
2011-10-31T15:25:32.683Z
A simple counting argument shows that for *any* representation of Boolean functions and any $n$, there will exist functions in $n$ variables whose representation takes at least $2^n$ bits.
Emil Jeřábek
CC BY-SA 3.0
2011-11-02T14:14:54.507Z
Thank you for your comments; I guess I was looking at it from the wrong (way too complicated) angle. It might be possible to extract some information about $f$, so I will look into that. If I succeed, I'll be back here :) Thanks again
Mike B.
<cc.complexity-theory><ds.algorithms><boolean-functions><upper-bounds>
Succinct representation of boolean functions
Mike B.
# Succinct representation of boolean functions

(Asked by: username_0 on 2011-10-29)

Let $f$ be a boolean function over $n$ variables $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}$. We are looking now for a representation of $f$ s.t. when given that representation and values $x\_1, \ldots, x\_n$, a turing machine in $PH$ can decide whether $f(x\_1, \ldots, x\_n) = 1$.

> What is the smallest representation of a boolean function meeting these requirements?

Circuits seem an intuitive choice, and a turing machine in $P$ can decide whether a set of values $x\_1, \ldots, x\_n$ satisfies that function. But circuits take upto exponential size in $n$, so we're hoping on smaller representations, given that the complexity of the machine calculating the result of the function can be much higher.

There are no bounds on the complexity of the function computing the representation.

**Tags:** cc.complexity-theory, ds.algorithms, boolean-functions, upper-bounds

> **Comments:**
> **username_1**: Isn't the trivial answer a binary string of length $2^n$? Unless you know something about your $f$, you cannot have anything smaller.  
> **username_2**: You're probably looking for the resource-bounded Kolmogorov complexity of the truth table of $f$.  
> **username_3**: A simple counting argument shows that for *any* representation of Boolean functions and any $n$, there will exist functions in $n$ variables whose representation takes at least $2^n$ bits.  
> **username_0**: Thank you for your comments; I guess I was looking at it from the wrong (way too complicated) angle. It might be possible to extract some information about $f$, so I will look into that. If I succeed, I'll be back here :) Thanks again  

---

## 0 answers

