8 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 $...
Ryan Williams's user avatar
8 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 ...
Michael Wehar's user avatar
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 $\...
Emil Jeřábek's user avatar
6 votes
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 ...
Neal Young's user avatar
  • 9,595
5 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 ...
holf's user avatar
  • 2,164
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 ...
Emil Jeřábek's user avatar
5 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,...
Mikolas's user avatar
  • 1,322
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 ...
Emil Jeřábek's user avatar
4 votes

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 ...
raki123's user avatar
  • 41
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 ...
Anupam Das's user avatar
2 votes
Accepted

Linear Integer Arithmetic Satisfiability with Three Literals

$(x< y) \land (y < z) \land (z < x)$
D.W.'s user avatar
  • 11.7k
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, ...
Sasha Kozachinskiy's user avatar
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.
Pushpa's user avatar
  • 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 ...
kodlu's user avatar
  • 2,070
2 votes
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 ...
Emil Jeřábek's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
cvalkan's user avatar
  • 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 ...
Michael Wehar's user avatar

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