Tag Archives: Difficulty 6

Inequivalence of Simple Functions

This paper (also referenced in our last problem) is the first one in the Bibliography whose first author started with “T”.  It feels weird that it took so long to get that letter.  Now the only letters missing in the Bibliography are “Q” (though I have a direct proof from Maurice Queyranne in the K-Closure post),  “X”, and “Z”.  I’m not sure I’ll get any “X” or “Z” papers, we’ll see.

The problem: Inequivalence of Simple Functions.  This is problem PO15 in the appendix.

The description: A simple function is a composition of basic functions on non-negative integers from:

  • s(x) = x+1
  • plus(x,y) = x+y
  • sub(x) = x-1
  • selecti (x1..xn) = xi
  • div(x,t) = [x/t] (integer division where t is a constant positive integer)
  • w(x,y) = if(y == 0) then x else 0
  • mod(x,t) = The remainder of dividing x by t (t is a constant positive integer)

We are given two simple functions f and g over some set of initial variables X.  Can we provide starting values in X that give different outputs for f and g?

Example:

Let

f(x,y) = s(s(s(x)))

(This returns x+3)

g(x) = s(s(s(w(x,y))))

(This returns x+3 if y is 0, but 3 if y is not 0)

On any input pairs (x,y) where y is 0, f and g will return the same value.  But the functions are inequivalent because f(2,7) = 5 but g(2,7) = 3.

Reduction: Tsichritzis uses Inequivalence of Loop Programs Without Nesting, which we did last time.  The idea is to show that all such program actually define simple functions (and so therefore if we can find the simple function derived from a program, that is our reduction).

First, he shows that a program without loops either returns xi + k, or k, where xi is some variable and k is a constant.  The idea is that since we can only do three things, each command can be rewritten from the top down:

  • If the instruction you are looking at is an assignment X=Y, then replace that with X=A (where A is whatever value Y is.  Either it has been computed previously in the program, or is Y’s starting value
  • If the instruction you are looking at is an increment X=X+1, then replace that with X=A+1, (where A is whatever the previous value of X is.  Either it has been computed previously in the program, or is X’s starting value)
  • If the instruction is X=0, then remember that 0 is the most recent previous value of X.

At the end, we look at what the output variable has been updated to.  It can only have been changed by some amount of additions to some variable’s start value, or by some amount of additions to 0.

So what is left is what goes on inside a loop.  Since loops cannot be nested, we know that the body of the loop only has the basic instructions.  Thus, all a loop can do is, for each variable Yi:

  1. Leave it alone, so, if yi was the contents of the variable at the beginning of the loop, Yi = yi at the end of the loop.
  2. Reset the value to some new constant k
  3. Set it to some other variable Yj‘s initial value yj plus some constant k.  We’ll say in this case that variable Yi links variable Yj

It’s possible for this set of linking to form a cycle.  It’s also possible for variables to depend on variables inside a cycle, but not to be in the cycle themselves.  The third possibility is for as variable to not care about a cycle at all and be independent.  The values of the independent variables are easy to express as simple functions.

If we have a cycle, the paper shows how the changes to the variable in one iteration can get added together by everything in the cycle, and then multiplied by the number of iterations the cycle goes.  These can also be represented as simple functions.

Difficulty: 6  The actual task we’re trying to do (“represent this program as a simple function”) is pretty easy to see.  The details of how to write the simple functions are pretty finicky, though.

 

Inequivalence of Programs with Arrays, Inequivalence of Programs with Assignments

Both of these problems are from the same paper and use basically the same proof, so we’ll do them together.

The Problems: Inequivalence of Programs With Arrays (PO11 in the appendix) and Inequivalence and Programs with Assignments (PO12 in the appendix)

The Description (for Inequivalence of Programs With Assignments): 

Given two programs P and Q that access a common set of variables, S.  Each statement in the program is of the form “x0 <- if x1 = x2 then x3 else x4“, where each xi is a variable from S.  Will the two programs always give different output for all initial variable configurations?

The Description (for Inequivalence of Programs With Assignments):

Same idea, but the possible statements in the program are:

  • Select an element B of an array α: A <- α.B
  • Update an element B of an array α: α.B <- A
  • “Operate” on an operation Φ: A <- Φ B1B2..Bk.  Φ comes from a given finite set of operations and is expected to take a certain number of arguments (k) that we know ahead of time.

Example: The “outputs” of these programs are the final values of the variables.  They denote a “final” value by representing a program as a Directed Acyclic Graph, and the leaf nodes (of outdegree 0) are the variables with final values.  We will specify what variables we care about as output variables

So for example, we might have the one-line program:

k <- if i=j then 2 else 3

Compared to the one-line program:

k <- if i=j then 3 else 2

If k is our output variable, then for all values of i and j both programs will produce different outputs.  If we change our second program to:

k<- if i=j then 2 else 2

…then if we assign i and j the same values, both programs will give the same output.

Reduction (for Inequivalence of Programs With Assignments): Downey and Sethi use 3SAT.  If we start with a formula with variables y1..yn we will create a program with variables {T,F, A1..An, B1..Bn,).  Then we just write a program that checks if all clauses are true.  “D” will be our output variable and will be updated for each clause.  We start it as true initially:

D <- if T = T then T else T // D is true so far

Then we check the first clause.  A variable “C” will be used for each clause.  It starts out false and will be set to true once the clause is satisfied:

C <- if F = F then F else F // C is false so far

Then for each literal x1..x3 we check if it has been made true.  We use Ai if the literal is positive in the clause and Bi if the literal is negative in the clause.  So suppose our clause was (y1, ~y2, y4), we’d have the lines:

// does the first literal make the clause true?
C <- if A1 = T then T else C
// does the second literal make the clause true?
C <- if B2 = T then T else C
// does the third literal make the clause true?
C <- if A4= T then T else C

C now is true if and only if the clause is satisfied, so let’s update D:

// D becomes false if we don't satisfy that clause
D <- if C = T then D else F

We then repeat that process for each clause.  At the end, we add rules saying that a variable and its negation can’t both have the same value:

D <- if A1 = B1 then F else D

..repeated for each variable.

The final output of this program is D, which will be true if our inputs legally satisfied the formula, and false otherwise.

Our second program just outputs the constant “F”.  The programs will produce different outputs if and only if there is a way for the first program to produce a T, which happens when D is true, which happens when all clauses are true, which happens when the formula is satisfiable.

Reduction (Inequivalence of Programs With Arrays): The same program works, we just need to replace our assignment if operations.  We do this by placing all of the elements of what we are comparing into an array, and replacing the statement “E <- if A=B then C else D” with:

α.A <- D
α.B <- C
E <- α.A

..if A and B are the same, then we will fill that spot in the array with D then C, and get a C out.  Otherwise, the two assignments go to different locations, and E is set to what is in the array at position A, which is the value D.  Since we can go back to the previous reduction and replace all of its statements with 3 statements under the new rules, the reduction works in the same way.

Difficulty: 6.  This isn’t a hard reduction to do, I think the hardest thing is to get students to think in terms 0f the restrictions these programs require.  There are no loops or anything (that would make this problem undecidable, at least in general), and representing variables as positions in an array is something we might be used to doing if all variables are integers, but since variables here are things like “B2” some work might need to be done to convince students that the mapping to integers for all variables is reasonable.  It’s not a thing we do as much with modern high-level languages as we might have done in the 1970s when the underlying machine was much more exposed.

Ensemble Computation

This next one is done as an example of “Local Replacement” in the main part of the G&J book, but it’s pretty complicated, so I figured it was worth a post.

The problem: Ensemble Computation.  This is problem PO9 in the appendix and is done on pages 66-68 of G&J.

The description: Given a set A, and a collection C os subsets of A, and a positive integer J.  Can we find a sequence z1..zj, of at most J elements, where:

  • Each zi is formed as the union of 2 disjoint sets xi and yi
  • Each xi and yi is either (the set containing) a single element of A, or a zk for some k < i
  • Every set in C appears as a zi someplace?

Example: G&J say that this problem comes out of a desire to minimize the number of multiplications needed to compute a set of products- the idea being that the union of 2 sets works like the multiplication of the sets with those terms.  So let’s suppose A = {a,b,c,d,e}, and C = {ab, bcd, ce}

(Really C should be a collection of sets like {a,b}, but I think that thinking of it as multiplication is helpful)

Then a sequence that might get everything in C might be:

  • z1 = ab
  • z2 = bc
  • z3 = bcd
  • z4 = ce

..which is the best we can do.  But now imagine that the second element of C was “abc” instead of “bcd”.  Then we can make the sequence:

  • z1 = ab
  • z2 = abc
  • z3 = ce

.. Using the z1 result as an operand to create our z2, enabling us to do it in fewer steps.

Reduction: G&J use Vertex Cover.  So we’re given a graph G=(V,E) and an integer K.  Our set A will be the set of all vertices in V, plus a new element a0.  For each edge (u,v) in E, we will create a set {a0, u, v} in C.  Our bound J will be set to K + |E|.

Suppose G has a vertex cover of size K (we’ll call them v1 .. vk).  Then we know that each edge in E can be built using at least one of the VC vertices.  So the following sequence will work and be of size J:

  • z1 through zk are formed by unioning a0 with the VC vertex vi (i=1..k)
  • Each of the remaining unions will make an element of C (based on an edge in E) by unioning the z set that has the VC vertex in the edge with the vertex in A that has the other end of the vertex.

In the other direction, suppose we have a sequence of unions z1..zj that solves the Ensemble Computation problem.  There may be multiple possible solutions to this problem, let’s look at the shortest sequence, and also the one that has the least number of operations that make a z set out of 2 elements of V (and not a0)  It turns out that since we have a minimum length sequence, the only reason to union 2 elements u and v from V together would be because (u,v) is an edge in E, and we want to union in a0 later to make the set {a0, u, v} in C.  But then we can rearrange the order and union a0 with u first, and union that result with v to get the same element of C in the same number of steps.  So this means that our sequence has 2 kinds of operations:

  1. Unions of some vertex with a0
  2. Unions of one of the above sets with a vertex to make an element in C.

We know that there are |E| of the second kind of union (because there are |E| elements in C), and so there must be K of the first kind of union.  So the vertices we union directly with a0 must be of size K, and since one of them gets combined in each set in C (and thus is a part of each edge in E), must be a vertex cover.

Difficulty: 6. This is one of those “the description is harder than the actual problem” problems.  All of the talk of sequences and unions and things looks scary, but the actual problem isn’t that bad.  As for the actual reduction, I think it would be a good hard homework problem.  One trap I see is that the need for a0 might not be obvious (it’s there to force us to “choose” the VC vertices and commit them to be a step in our sequence).  So maybe that needs to be a hint.

Protected: Code Generation With Unlimited Registers

This content is password protected. To view it please enter your password below:

Protected: Code Generation on a One-Register Machine

This content is password protected. To view it please enter your password below:

Protected: ETOL Language Membership

This content is password protected. To view it please enter your password below:

Protected: Structural Inequivalence for Linear Grammars

This content is password protected. To view it please enter your password below:

Protected: Two-Way Finite State Automaton Non-Emptiness

This content is password protected. To view it please enter your password below:

Protected: First Order Subsumption

This content is password protected. To view it please enter your password below:

Protected: Minimum Axiom Set

This content is password protected. To view it please enter your password below: