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 $...
- 26.7k
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 ...
- 5,025
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 $\...
- 15.4k
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,535
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
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,049
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 ...
- 15.4k
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 ...
- 15.4k
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
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,\...
- 11.1k
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 ...
- 121
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 ...
- 181
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 ...
- 8,223
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,039
2
votes
Accepted
Linear Integer Arithmetic Satisfiability with Three Literals
$(x< y) \land (y < z) \land (z < x)$
- 11.1k
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
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 ...
- 15.4k
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,025
Only top scored, non community-wiki answers of a minimum length are eligible