# Tag Info

• 17.9k
Accepted

### Complexity of Maximizing Hamming Distances Below a Threshold

Lemma 1. The problem is NP-hard, by reduction from Max-2-SAT. Proof sketch. The reduction is in two steps. Consider the variant of the problem in which $d$ is even and the coverage requirement is ...
• 10.8k
Accepted

### Treewidth relations between Boolean formulas and Tseitin encodings

There is a relation between the treewidth of a circuit and the primal treewidth of its Tseitin transformation but you will have to take the fan-in of the circuit into account, which is large when ...
• 2,174

### XORSAT to HornSAT reduction

You can’t do this. By Schaefer's dichotomy theorem, satisfiability of sets of XOR clauses mixed with Horn clauses is an NP-complete problem, hence it does not have a poly-time reduction to Horn-SAT ...
• 17.9k
Accepted

### Minimum Unsatisfiable Core

First thing to say that the minimality here is subset-minimality (as opposed to cardinality-minimality). Observe that minimality is not actually needed. The main objective is to block the assignment A,...
• 1,322

### Relationship between size of Boolean functions and DFAs

Complementing the other answers, here are a few research papers that explicitly study the size of (one-way) DFAs that represent Boolean functions in the way the OP describes. Maximum and average state ...
• 6,545

### Relationship between size of Boolean functions and DFAs

Regarding question 3: There are $S^{2S} \cdot 2^S$ different DFAs on $S$ states (fixing the initial state), and so most Boolean functions require $\Omega(2^n/n)$ states. This is the same calculation ...
• 14.5k

### Relationship between size of Boolean functions and DFAs

Here are are my attempts to answer. I'm not an expert on this subject. Please check all details for yourself. No. Consider $f$ defined by $f(x)=1$ iff $x_1 \ne x_{n/2+1}$ or $x_2 \ne x_{n/2+2}$ or ...
• 12.2k
Accepted

### Is there a generalized SAT problem for higher-order logics?

Yes, you may be interested in the paper "Higher-Order Quantified Boolean Satisfiability" by Chistikov, Haase, Hadizadeh, and Mansutti (https://doi.org/10.4230/LIPIcs.MFCS.2022.33)
• 1,337
Accepted

### Efficient transformation into CNF preserving entailment

This is impossible in polynomial time unless P = NP. Such a transformation would give a reduction of the coNP-complete validity problem $\{\psi:\top\models\psi\}$ to the polynomial-time decidable ...
• 17.9k

### Treewidth relations between Boolean formulas and Tseitin encodings

Actually, we can transform any Boolean Circuit $C$ that uses only $\wedge$, $\vee$, and $\neg$ gates of treewidth $k$ into a CNF whose primal treewidth is within a constant factor of $k$, where this ...
• 41

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

I stumbled upon this question now, many years later. In the interim the following paper has appeared: https://dl.acm.org/doi/10.1145/3278158 https://arxiv.org/abs/1704.08705 There the authors do ...
• 171
Accepted

### Linear Integer Arithmetic Satisfiability with Three Literals

$(x< y) \land (y < z) \land (z < x)$
• 12.2k
Accepted

### Universal Boolean Formulas

A $O(2^n/\log n)$-size depth-3 universal Boolean formula was constructed in O.B. Lupanov. Complexity of the universal parallel-series network of depth 3. Trudy Matem. Inst. Steklov, 133:127-131, ...
Accepted

### Is there a standard format for Dependent QBF?

There is a standard format proposed. At QBFEVAL’18 there is a DQBF-track, which uses DQDIMACS from a paper by Föhlich et al on IDQ.
• 209

### Fourier decomposition in terms of another basis

As pointed out in the comments if $u\in \{\pm 1\}$ then $x=x(u) \in \{0,1\}$ where $$x(u)=\frac{1-u}{2},$$ with $x(-1)=1,$ and $x(1)=0.$ This will then yield f(x)=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in ...
• 2,070
Accepted

### Power of non-implicationally-complete Frege systems and Boolean equational calculus

$\let\eq\leftrightarrow\def\ru{\mathrel/}\let\ET\bigwedge$Frege systems are required to be implicationally complete to make all such systems p-equivalent, yielding a robust definition of the Frege ...
• 17.9k
1 vote
Accepted

### If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl

Observe that if a $k$-CNF $\Phi$ is equivalent to an $l$-DNF $\Psi$, then every term of $\Psi$ implies every clause of $\Phi$, i.e., they share a literal. If the Boolean function is not constant, pick ...
• 17.9k
1 vote
Accepted

### Solve 3CNF in Poly-Time with Satisfiability Oracle

hint: assign values to variables one at a time and call algorithm A on resulting formula. if the result of algorithm A is satisfiable or non-satisfiable what does that mean about last variable ...
• 26
1 vote

### Correlation between noise resilience and output distribution of Boolean circuits

I have found some hints on my question in Moshe Looks, Competent Program Evolution, p. 31: Most local perturbations of large random formulae have no effect – 96% of them for arity five, and 91% for ...
• 31
1 vote

### Quantified Boolean Formulas with logarithmic alternations

A shorter answer. Initial observations: The problem is hard for every level of the polynomial hierarchy. The problem is hard for alternating Turing machines with $\log(n)$ alternations ...
• 5,127

Only top scored, non community-wiki answers of a minimum length are eligible