3
$\begingroup$

Straight to the point: I'm looking for a reference for the fact that the complexity of a read-once branching program solving the search problem for an unsatisfiable formula $F$ is at least the complexity of a read-once branching program solving the search problem restricted to critical assignments for $F$.

Definitions and formal statement are below.

Search problem: Let $F=C_1\,\wedge\, C_2\, \wedge\, ... \,\wedge\, C_m$ be an unsatisfiable formula. The search problem for $F$ is defined as follows: Given an assingment $\sigma:X\rightarrow \{0,1\}$, return a clause that is falsified by $\sigma$.

So, formally, the search problem can be described by a relation $R_F \subseteq \{0,1\}^n \times \{C_1,..,C_m\}$, such that $(\sigma,C_i)\in R_F$ if and only if $\sigma$ falsifies $C_i$.

Critical Assignments: Now a critical assignment is an assignment $\sigma$ that satisfies all clauses but one. Therefore, given such an assignment $\sigma$, there is a unique $C_i$ such that $(\sigma,C_i)\in R_F$. As a consequence, if $S$ is the set of critical assignments, then $Q_F = R_F \cap S\times \{C_1,...,C_m\}$ is a function.

Read Once Branching Program associated with $F$: A read-once branching program is a directed acyclic multigraph with a distinguished source vertex, of in-degree $0$ and distinguished sink vertices of out-degree $0$. Each non-sink vertex is labeled with a variable, and each sink-vertex is labeled with a clause. Each non-sink vertex labeled with a variable $x$ has two out-edges, one labeled with assignment $x=0$ and the other with assignment $x=1$. Such branching program is read-once if for each path $p$, each variable labels at most one vertex of $p$.

Each assignment $\sigma$ naturally defines a path from the source of the branching program to the a sink vertex. This is the path whose edge assignments are consistent with $\sigma$. The clause associated with $\sigma$ is the clause $C(\sigma)$ labeling the sink-vertex corresponding to $\sigma$.

Let $R\subseteq R_F$. We say that such a branching programs solves $R$ if for each assignment $\sigma$, the pair $(\sigma,C(\sigma))\in R$.

Wanted Reference:

Statement: The minimum size of a branching program solving $R_F$ is at least the minimum size of a branching program solving $Q_F$.

In other words the complexity of a read-once branching program solving the search problem for $F$ is at least the complexity of a read-once branching program solving he search problem restricted to critical assignments.

I would like to have a reference for the statement above. I have seen similar statements mentioned in several places. But I can't remember of a concrete reference clearly stating the fact above.

Question: Which article / book has a proof for the statement above? Or at least a proof for a similar statement?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.