3
$\begingroup$

In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has been strengthened later, showing that, in the limit, almost all boolean functions have exponential circuit complexity. It is often said that, even in 2022, we still cannot construct a single example of such a function. I'm interested in, and slightly confused about, the state-of-the-art in research on this question. In particular:

  • Wikipedia [2] states that "complexity theorists have only been able to prove superpolynomial circuit lower bounds on functions explicitly constructed for the purpose of being hard to calculate" which seems to contradict that no explict function is know.

  • Are there any candidate boolean functions (or family of functions) that are conjectured to have exponential circuit complexity, but where this has not been proven?

  • What is the state of exhaustive exploration of the circuit complexity of $n$-ary boolean functions? Presumably there is some small $n$ such that this complexity has been computed for all $i<n$?


  1. C. E. Shannon, The synthesis of two-terminal switching circuits https://ia802700.us.archive.org/6/items/bstj28-1-59/bstj28-1-59.pdf
  2. Wikipedia entry Circuit complexity https://en.wikipedia.org/wiki/Circuit_complexity#History
$\endgroup$
0

1 Answer 1

3
$\begingroup$

The best known lower bounds for explicit functions are $\Omega(n)$. The only superpolynomial lower bounds are in restricted models of circuits, such as monotone circuits and bounded-depth circuits.

NP-hard problems are expected to have exponential circuit complexity $2^{n^{\Omega(1)}}$; this is a non-uniform version of the Exponential Time Hypothesis.

Since there are $2^{2^n}$ functions on $n$ bits, I doubt that even for $n = 5$ it is feasible to find the maximal circuit complexity exactly.

$\endgroup$
3
  • 1
    $\begingroup$ So the Wikipedia page is misleading, and your 2nd sentence should replace the sentence I cite. $\endgroup$ May 8 at 17:40
  • $\begingroup$ Is there really no (vaguely) non-trivial result of the form: if an $n$-ary boolean function has exponential circuit complexity, then $n$ must be bigger than $x$ for some concrete $x$? $\endgroup$ May 8 at 17:41
  • 2
    $\begingroup$ The phrase "exponential circuit complexity" is meaningless if you fix $n$. $\endgroup$ May 8 at 19:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.