Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [boolean-algebra]

The tag has no usage guidance.

63 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
178 views

• 128
239 views

### Simple example of exponential gap between monotone and non-monotone circuits

Is there a simple example of a monotone Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone ...
• 160k
110 views

### Circuit complexity of hardest monotone function

Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such that the minimal size of a monotone circuit that computes $f$ is $\Omega(2^n / n^2)$. Use the fact that the number of ...
• 163
40 views

### How do I optimize a set of sub-lists which can combine to recreate higher level lists?

I am writing a function which XORs 32 boolean variables to produce a 32 bit output. To this end I have 32 lists of boolean variables (the lists have between 12 and 17 elements). Every variable in list ...
139 views

### Boolean function minimization

Does there exist a Boolean function for which no sum-of-products expression that minimizes the number of products also simultaneously minimizes the number of literals (counting repetitions)? ...
• 51
121 views

• 21