4
votes
Accepted
Is $f(X)f^d(X) = 0$ for a Boolean function $f$?
$$f^d(X)f(X) \lor f(X) \bar{x}_{n+1} \lor f^d(X) {x}_{n+1} = f(X) \bar{x}_{n+1} \lor f^d(X) {x}_{n+1}$$
The equality above comes from the general equality below. It has nothing to do with the context.
...
- 38.5k
3
votes
Accepted
Can Boolean circuits of polylog depth represent all Boolean functions?
A $k$-ary circuit of depth $d$ has size at most $k^d$, hence polylog-depth circuits of fan-in $2$ have quasipolynomial size. Thus, the vast majority of Boolean functions cannot be computed by such ...
- 955
3
votes
Shannon's result that some Boolean functions require exponential circuits
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-...
- 274k
2
votes
Accepted
How many different boolean functions exist up to permutation of its $n$ variables
You are looking for A003180.
The related sequence A003181 counts functions depending on all variables.
Often one allows further operations: negation of inputs, and negation of the output. The ...
- 274k
2
votes
sum of Boolean characters larger degree
This is related to higher-order Fourier analysis.
A classical result of Dickson ("Dickson's lemma") states that up to a change of basis, any quadratic form over $\mathit{GF}(2)$ is of the ...
- 274k
2
votes
Boolean function represented as a column vector: easy way to see if it has full degree?
Every function $f\colon \{0,1\}^n \to \{0,1\}$, whose input we style $x_1,\ldots,x_n$, has a unique expansion as a multilinear polynomial in the variables $y_i = (-1)^{x_i} = 1-2x_i$. It also has a ...
- 274k
2
votes
How to construct a carry-lookahead adder of the optimal $O(n)$ size
Actually, upon working on this problem for a bit more time, I discovered one method to build a size $O(n)$ and depth $O(\log n)$ CLA circuit. The key ingredient is the work-efficient parallel ...
- 31
1
vote
Accepted
Given a boolean circuit that computes a boolean function, can we always find an equivalent circuit with optimal size?
The problem is $\Sigma_2^P$-complete, which means that it is hard -- it is even "harder" than NP-complete problems. In particular, there is unlikely to be any polynomial-time algorithm. ...
D.W.♦
- 154k
1
vote
influence of neighourhood points
No. Suppose $h$ is the parity function and $f(x)=-h(x)$. Then $\sum_x h(x) f(x) = -2^n \le 0.5$, but
$\sum_i h(x) f(x) h(x^i) f(x^i) = n$ (which is as large as it can get) for all $x$.
D.W.♦
- 154k
1
vote
Accepted
Is there a notation for boolean algebra complexity?
This is called Circuit Complexity: https://en.wikipedia.org/wiki/Circuit_complexity
The size of a circuit is the number of gates it contains and its depth
is the maximal length of a path from an ...
- 2,469
1
vote
Time-complexity of evaluating a CNF formula
No. You can't even do it in $O(n^2)$ time, if $n$ is the number of variables. The formula might be much longer than $\Theta(n^2)$ (it might have many more clauses than that), and obviously any ...
D.W.♦
- 154k
Only top scored, non community-wiki answers of a minimum length are eligible