Here is another scheme problem with a different kind of a reduction.

**The problem: **Non-Containment for Free B-Schemes. This is problem PO18 in the appendix.

**The description: **A “B-Scheme is” a rooted, directed, acyclic graph where each vertex has outdegree of either 0 (a “leaf”) or 2 (a “test”). The test vertices label their out edges as “T” or “F”. Each vertex gets a label. Test vertices are labeled as boolean Boolean variables, leaves are labeled with function symbols (with the special symbol “Ω” meaning “undefined function”.

Multiple vertices can have the same label, but in a “free” B-scheme, no path from the root to a leaf hits two vertices with the same label. We can “assign” truth values to the boolean variables, which then define a path through the scheme to a leaf. The value of the truth assignment is the label given to the leaf we end up in.

Suppse we have two such B-Schemes, S_{1} and S_{2}. S_{1} is contained in S_{2} if for all assignments of variables, either S_{1} ends up in Ω, or S_{1} ends up in a leaf that is the same label as S_{2}‘s leaf with the same assignment.

So, our question is: Given two free B-Schemes S_{1} and S_{2}, is S_{1}* not* contained in S_{2}?

**Example:**

Here is our S_{1}:

“O” is the label for the Ω leaf

Here is S_{2}

(x1a and x1b both are labeled for the variable x1. I had to give them different names so Graphviz didn’t think they were the same variable.)

S_{2} returns the number of true assignments of x0 and x1. S_{1 }correctly finds the same leaf if at least one variable is true, but goes to O otherwise.

But, S_{1} is NOT contained in S_{2} because assigning both variables to true puts S_{1} in L1 and S_{2} in L2.

**Reduction: **The paper by Fortune, Hopcroft, and Schmidt defines this problem and reduces from 3SAT. First, we replace all positive occurrences of the same variable x_{i} with new variables u_{i1}..u_{ip} (if it occurred p times). We similarly replace all negative occurrences of x_{i} with v_{i1}..v_{iq} (if it appeared negated q times). Our job is to build two schemes.

S_{1}‘s job is to tell us if the formula is satisfiable. Each clause (a_{1},b_{1}, c_{1}), gets a chain of vertices. It goes “across” on F, and down to the first variable of the second clause on T. If all literals get assigned F, we end up in a Ω leaf. The final clause has edges from T to our output “f” leaf (Yes, that means the vertex we reach when the formula is satisfiable and all of the clauses are true is labeled “f”. I’m sorry.) Here is the paper’s example. Keep in mind that each of the a,b, and c vertices here represent literals whose actual value in the formula is one of the u and v variables we created above.

S_{2}‘s job is to make sure that all of our new u and v vertices have the same (and consistent) truth values. If we ever have a u_{i} with a different truth value than some other u_{j} (or if it has the same truth value as its corresponding v_{j}) we jump to f. If everything is ok, we jump to a new end point g. Here is the diagram from the paper. Notice that they are doing this for *all *of the replacements for *all* of the variables in one scheme.

If our original formula was satisfiable, we would find a way to make S_{1} go to f, and since all of the variable assignments are consistent, we could use those assignments to make S_{2} go to g, so S_{1} is not contained in S_{2}, In the other direction, if S_{1} is not contained in S_{2}, then since all S_{1} can reach is Ω and f, it must be the case that there is an assignment that leads S_{1} to f and S_{2} to g. S_{2} ends in g only when its u and v variables are assigned consistently. S_{1} goes to f only when its clauses are all satisfied. Thus, we have found a way to satisfy the formula.

**Difficulty: **7. This is different from the other scheme problems we have seen, where the second scheme is the trivial “yes” scheme. Here, we need to use both schemes to check different aspects of the solution. That’s pretty cool.