# Tag Info

11

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 was established by Lupanov, and his method is known as the Lupanov representation of boolean functions. It also gives an upper bound of $(1+o(1))2^n/\log n$ ...

7

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 $poly(n)$ bits, and do an argument similar to Savitch's theorem. Every two alternations will divide the running time of the computation by a $poly(n)$ factor. I ...

7

(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 following: The problem is $NSPACE(log^2(n))$-hard. (3) Here is my informal justification for the preceding assertion: Given a $log^2(n)$ space bound NTM and an ...

6

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 theorem this result would imply that NP = RP. To solve UNAMBIGUOUS-SAT, recall that $a \oplus b$ implies $a \neq b$. Find the XOR relationship between each pair ...

6

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 $\Phi$ and $\Psi$ may be arbitrary monotone formulas. In this case, there is a poly-time ctt reduction from TAUT to the problem that preserves the number of ...

5

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 \land B)$ and $(A \land \bar{B})$ are. The read-once decision tree for $\bar{A}$ can be obtained from the read-once decision tree for $A$ by switching $True$ and $... 4 As Kyle Jones has mentioned, the example you provided is called (restricted) resolution. Beside that, pure literals can also be safely removed from a SAT problem. Unit clauses can be assigned a truth value. Check this paper: The Puzzling Role of Simplification in Propositional Satisfiability. Inês Lynce and João Marques-Silva. It discusses several ... 4 If you really want to enumerate all the assignments, then you really need to find a satisfying assignment and then block it by a clause. E.g. if you find a satisfying assignment$a_1=a_2=a_3=0$you'd block it by$a_1\lor a_2\lor a_3$. One, relatively easy improvement, is to reduce the found assignment to a (prime) implicant. For instance, if$a_1\rightarrow ...

4

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, which led to the conflict. However minimality is beneficial because like this you block other "bad" assignments as well. Similarly, multiple MUCs are not a ...

4

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,\dots,x_n) = (x_1-z_1)^2 + (x_2-z_2)^2 + \dots + (x_n-z_n)^2.$$ Based on this, we can easily construct a function $g : \{0,1\}^n \to \mathbb{R}$ that is zero at ...

3

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 gates will give you a circuit calculating that function. This however does not actually give you a minimum sized circuit. Karnaugh maps minimize the number ...

3

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,...1),(1,0,...,1),...(1,1,...,0)$ if yes, build a dum false instance of your problem. Otherwise build: $$\phi' =( \phi ) \lor (x_1 \land ... \land x_n)$$ Which ...

3

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 if and only if $\phi$ is unsatisfiable. Therefore, any polynomial-time algorithm for your problem would imply P=NP. If you don't like relying on the special ...

3

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 the strings \begin{align} u_k&={+}^{m-k}{*}{+}^k,\\ v_l&=1^{l+1}0^{m-l+1}. \end{align} Notice that $u_kv_l$ is a well-formed Boolean sentence for ...

3

As pointed out by the OP (user13772), this is false. Jukna et al. constructed explicit Boolean functions $f$ that require deterministic decision trees of size $2^{\Omega(\log^2 N)}$, where $N$ is the number of monomials in a minimal DNF for $f$ and $\lnot f$. Note that every Boolean function on $n$ inputs can be expressed as a deterministic decision tree ...

3

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 precisely what Kaveh asks for in his question 2: they give a (uniform) TC0 algorithm for balancing, hence obtaining an alternative proof of the main result in Buss '...

3

I am not sure if this is very relevant but in Log-Space Algorithms for Paths and Matchings in k-Trees (building on a long history of past work and specifically on Arithmetizing classes around NC1 and L by Limaye-Mahajan-Rao) we show how to find recursive balanced separators for a tree in Logspace. This bound may very well be improvable to $\mathsf{NC}^1$ if ...

2

That's right. If $n$ is the subset you're interested in, then there are, as you said, $2^{|n|}$ possible assignments. If you don't want to go through all those possibilities, you can use various optimization techniques to essentially decrease the size of $n$. Look at the Quine–McCluskey algorithm and K-maps, for example minimization techniques.

2

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 variables and leaves by $0$ and $1$. Left branches are the "then" part setting the variable to true and right branches are the "else" part setting it to false. ...

2

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.

2

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 \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ and if we denote the $\{0,1\}$ valued version of $f$ as $\tilde{f},$ \frac{1-\tilde{f}(x)}{2}=2^{n-1}f(0)-\...

2

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, 1973 (In Russian) In this paper Lupanov uses language of parallel-series networks, which is equivalent to De Morgan formulas with unbounded fan-in AND, OR ...

1

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 arity ten (the drop is a corollary of the increase in the percentage of unique behaviors in a fixed size sample as the arity increase). This is a consequence of ...

1

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 that run for polynomial time. Deeper Insights: Suggested by Kaveh's comment above, the problem can encode computations for $AltTime(\log(n), n)$ ...

1

These things are called variable and literal (in)dependence. To check that a literal/variable is dependent is in NP [1]. [1] Propositional Independence - Formula-Variable Independence and Forgetting. available at arxiv

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