11 votes
Accepted

May Boolean circuits be exponentially more concise than Boolean formulae?

The circuit complexity of any boolean function of $n$ variables is at most $(1+o(1))2^n/n$, so a separation of between circuit and formula complexity of $\Omega(2^n)$ is not possible. This upper bound ...
7 votes

Quantified Boolean Formulas with logarithmic alternations

Building on Michael Wehar's answer, it seems that you can easily show that $NTISP(n^{\log n},poly(n))$ computations can be encoded in polysize such QBFs: you use $O(\log n) $ alternations, each of $...
7 votes

Quantified Boolean Formulas with logarithmic alternations

(1) What we already know: As you've already stated, QBF with $\log(n)$ alternations of quantifiers is hard for every level of the polynomial hierarchy. (2) I think that we can also prove the ...
6 votes
Accepted

Conversion between k-SAT and XOR-SAT

If all XOR relationships between variables in CNF formulas could be detected in polynomial time, then this would allow the solution of UNAMBIGUOUS-SAT in polynomial time. By the Valiant–Vazirani ...
6 votes
Accepted

The problem of deciding whether a monotone CNF implies a monotone DNF

Assuming SETH, the problem is not solvable in time $O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$ for any $\epsilon>0$. First, let me show that this is true for the more general problem where $\...
5 votes

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 ...
5 votes
Accepted

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

I found a partial solution. The problem is in L. The negation of $A \leftrightarrow B$ is equivalent to $(\bar A \land B) \lor (A \land \bar{B})$ which is equivalent to $False$ iff both $(\bar A \...
  • 686
4 votes
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 ...
4 votes
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,312
4 votes
Accepted

Complexity of generating a pseudo-Boolean function

There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely, $$f_z(x_1,\...
  • 10.5k
3 votes

Symbolic Execution of the Quine-McCluskey Algorithim

Since you stated your purpose is considering circuit bounds: Taking a boolean function and "minimizing" using Karnaugh maps or the Quine–McCluskey algorithm, then converting the formula to AND and OR ...
3 votes

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

The first part of the question leads to a coNP-hard problem; this is a reduction from UNSAT. Suppose that $\phi$ is a SAT formula with $n$ variables. Check if it is satisfied by $(1,1,...,1),(0,1,......
3 votes

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

Well, I don't know what the exact complexity class is, but the problem is hard: a polynomial-time algorithm for this problem would imply P=NP. Just take $k=0$; then the answer to your problem is yes ...
  • 10.5k
3 votes
Accepted

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

The answer to all three questions is negative. Consider e.g. the prefix version (3), and assume for contradiction that it is decidable by a (wlog deterministic) automaton $A$ with $m$ states. Consider ...
3 votes

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 ...
3 votes
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 ...
  • 1,854
2 votes
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
2 votes

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,016
2 votes

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

From a ITE formula $\phi$, you can compute polynomially a reduced assignment list to describe all valuations which makes it true. To do that, just look at your formula as a tree with nodes labeled by ...
  • 7,757
2 votes
Accepted

Linear Integer Arithmetic Satisfiability with Three Literals

$(x< y) \land (y < z) \land (z < x)$
  • 10.5k
2 votes
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, ...
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 ...

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