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.

  • 16
    $\begingroup$ Isn't the trivial answer a binary string of length $2^n$? Unless you know something about your $f$, you cannot have anything smaller. $\endgroup$ – Jukka Suomela Oct 29 '11 at 10:50
  • 1
    $\begingroup$ You're probably looking for the resource-bounded Kolmogorov complexity of the truth table of $f$. $\endgroup$ – MCH Oct 30 '11 at 20:59
  • 4
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Oct 31 '11 at 15:25
  • $\begingroup$ 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 $\endgroup$ – Mike B. Nov 2 '11 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.