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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.