The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
163 views

May Boolean circuits be exponentially more concise than Boolean formulae?

Consider a family $(f_n)_{1 \leq n}$ of Boolean functions, where $f_n$ is a function on $n$ variables. Consider for every $n$ the smallest Boolean formula $F_n$ describing $f_n$, and the smallest ...
4
votes
3answers
112 views

Remove unneeded atoms in CNF minimalization (SAT preprocessing)

This might be a very basic question. I am interested in all atoms of a propositional formula that can be removed from a particular formula, while the derived formula has the same satisfiability ...
2
votes
2answers
101 views

Number of SAT checks that are needed to find all combinations of subset of boolean variables of a propositional formula

Please mind that I sometimes lack formal mathematical knowledge and English is not my first language, so I might miss the right words. Please change the tile if needed. Also, I have choosen this site ...
4
votes
0answers
394 views

k-CNF ←→ k-DNF conversion to minimize errors

the following problem/question seems fundamental/hard. it appears in some circuit theory proofs, graph theory, and maybe elsewhere. looking for any nontrivial insight. will add various known/nearby ...
2
votes
2answers
203 views

Size of decision tree for f is polynomial in the DNF size of f and CNF size of f

I've been having hard time with proving the following claim: Let $f:\{T,F\}^n\rightarrow \{T,F\}$ be a boolean function. Let $size_{DT}(f)$ denote the number of leaves in the smallest (w.r.t the ...
9
votes
1answer
214 views

Boolean formula balancing in $\mathsf{AC^0}$

I am looking for references about the complexity of Boolean formula balancing problem. In particular, Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$? Is there a simple proof ...