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 $...
- 27.3k
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 ...
- 5,127
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 $\...
- 16.9k
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 ...
- 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 ...
- 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 ...
- 16.9k
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,...
- 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 ...
- 16.9k
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 ...
- 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 ...
- 161
2
votes
Accepted
Linear Integer Arithmetic Satisfiability with Three Literals
$(x< y) \land (y < z) \land (z < x)$
- 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, ...
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,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 ...
- 16.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 ...
- 16.9k
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