Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
  • 10.8k
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,174
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
5 votes

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 ...
Hermann Gruber's user avatar
5 votes

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 ...
Yuval Filmus's user avatar
  • 14.5k
5 votes

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 ...
D.W.'s user avatar
  • 12.1k
4 votes
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)
Bartosz Bednarczyk's user avatar
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
  • 12.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, ...
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
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 ...
floating'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