The tag has no wiki summary.

learn more… | top users | synonyms

11
votes
2answers
213 views

What is the complexity of the equivalence problem for read-once decision trees?

A read-once decision tree is defined as follows: $True$ and $False$ are read-once decision trees. If $A$ and $B$ are read-once decision trees and $x$ is a variable not occurring in $A$ and $B$, ...
2
votes
3answers
158 views

How hard is it to find a “well-distributed” subset of models of a propositional formula?

We consider the propositional language $\mathcal{L}_{\mathit{PS}}$ defined over a finite alphabet $\mathit{PS}$ and the usual logical connectives. An interpretation is an assignment $\mathit{PS} ...
10
votes
0answers
207 views

Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2

Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and ...
1
vote
1answer
66 views

What is the complexity of the set of closed boolean tautologies assuming well formed formulae?

Let's define two CFGs: S ::= 0 | 1 | (S+S) | (S*S) S' ::= 0 | 1 | S+S | S*S | (S) And two languages: M = { w | S generates w, and w evaluates to 1 } ...
7
votes
1answer
160 views

Conversion between k-SAT and XOR-SAT

According to XOR Satisfiability Solver Module for DPLL Integration by Tero Laitinen, we need $2^{n-1}$ CNF clauses to convert an $n$ literal XOR-SAT clause if we do not want to increase the number of ...
5
votes
1answer
187 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
122 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
119 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
495 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
215 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
237 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 ...