Tag Archives: 3SAT

Cyclic Ordering

This problem is very similar to the Betweenness problem from last time, with a slightly different ordering rule.

The problem: Cyclic Ordering.  This is problem MS2 in the appendix.

The description: Given a set C of triples (a,b,c) from some universal set A, can we find an ordering f of the elements of A, so that for each triple in C, either:

  • f(a) < f(b ) < f(c)
  • f(b) < f(c) < f(a)
  • f(c) < f(a) < f(b)?

Example: Like last time, let’s say A = {a,b,c,d,e,f}.  Here are some triples:

(a,b,c)
(e,b,c)
(a,e,f)
(e,f,a)
(d,f,c)

The usual lexicographic ordering of elements of A will satisfy these triples.

A triple that won’t work with that ordering is (a,e,b).  But an ordering {a,e,b,c,d,f} would satisfy all triples including this new one.

Reduction: Galil and Megiddo use 3SAT.  So we start with a formula with p clauses (each clause is xi∨ yi∨ zi) over r variables (u1..ur, and their negations).  Order each clause so that the variables in it are in increasing order of their subscript.  Our set A will have 3 elements for each variable ui: αi, βi and γi. It will also have 5 additional elements for each clause (these will be the j through n described below)

Each variable is “associated” with a triple from these elements of A.  The positive version of the variable ui is associated with (αi, βi, γi).  The negated version of the variable ~ui is associated with the triple (αii, βi).  These triples won’t get added to C,  but will be the basis of the triples each clause adds to C.

So suppose we have a clause x∨y∨z.  Each of these literals has a triple associated with it as defined above.  Let’s call those triples (a,b,c), (d,e,f), and (g,h,i).  Using those 9 symbols plus the “extra” symbols for this clause j,k,l,m, and n, create the following triples, called Δ0: {(a,c,j), (b,j,k}, (c,k,l), (d,f,j), (e,j,l), (f,l,m), (g,i,k), (h,k,m), (i,m,n), (n,m,l).  These triples, for each clause, create our set of triples C.

Now, suppose we have an assignment of variables- a set S of ui and ~ui that has exactly one choice for each i.  For each clause, build a set of triples Δ out of Δ0 and the triples associated with the literals not in S.  Then if S includes a literal that makes the clause true, there is a way to satisfy every ordering in Δ.  They show this with a table giving the possible assignments.  Here are 2 examples:

  • If S has just x in it (and not y and z), then Δ adds the triples (a,c,b), (d,e,f), and (g,h,i) and the ordering ackmbdefjlnghi will satisfy all triples.
  • If S has y and z in it (and not z), then Δ adds the triples (a,b,c), (d,f,e), and (g,i,h) to Δ0, and the ordering abcjkdmflnegih will satisfy all triples.

In the other direction, if a clause is not satisfied by this assignment, then none of its literals are in S, and so we form Δ by adding the triples (a,b,c), (d,e,f), and (g,h,i) to Δ0.  But if we had an ordering of the elements of A that satisfied the triple (a,b,c), it must also satisfy the triple (a,c,j) from Δ0.  This means that (b,c,j) is effectively a triple as well (the ordering has to satisfy that triple as well).  Since (b,j,k) is in Δ0, then (c,j,k) is effectively a triple, and since (c,k,l) is in Δ0, we can conclude that (j,k,l) must also satisfy the ordering.

We can perform a similar analysis to eventually conclude that (l,m,n) must also satisfy the ordering.  But we have the triple (n,m,l) in Δ0, and there is no way to satisfy both consistently.  Thus, if a clause is not satisfied, there is no legal ordering to satisfy all of the triples in Δ.

Taking this analysis and applying it to all clauses completes the reduction.

Difficulty: 8.  It’s not obvious, at all, even looking at the problem, how you can come up with these different triples.  I can (mostly) follow the logic and see that it works, but wow, coming up with this must have been a huge pain.

Programs With Formally Recursive Procedures

This is the last of the “Program Optimization” problems, and the next section is the last one on “Miscellaneous” problems, which has 19 problems in it.  So, unless some diversion into a problem not in the book happens, we’re on the countdown through the last 20 problems!  The end is in sight!

The problem: Programs with Formally Recursive Procedures.  This is problem PO20 in the Appendix.

The description: Given a set of function definitions and a program that makes a sequence of function calls using those definitions (the paper by Winklmann uses Algol because he wrote it in 1982.  But any language that allows recursion should work).   Are any of the procedures in the program formally recursive?  For our purposes, “formally recursive” means that there exists a chain of calls that has a call to a function higher in the chain (not necessarily a parent, any ancestor will do).

My first instinct was to wonder if this problem was actually undecidable.  It’s not because we will have some fixed # of procedures d, and so any call chain needs to be checked only to depth d+1- if we get that far, we must have a repeat someplace.  If we never get that far, we can back up and check other call chains, eventually checking all of the paths through the call tree exhaustively.  The proof that the problem is in NP is in the paper, but it involves representing the call tree as a DAG so we can use one vertex for two equivalent paths.  Winklmann says that if you do that the number of vertices is “bounded” by the number of procedures in the program (he doesn’t say what that bound is, though).

Example: It’s hard to make a small example that’s not obvious.  How about this:

E(){
  E();
}

D(){
}

C(){
 A();
}

B(){
 D();
}

A(){
 B();
 F
}

main(){
  A()
}

If “F” is replaced by a call to C, the program is formally recursive, because the call chain main->A->C->A has a repeat.  If we replace that F with another call to B the program is not formally recursive because even though recursive functions like E exist (and even though B gets called twice in two different chains), there is no call chain that will start at main and hit E (or anything) more than once.

Reduction: Winklmann uses 3SAT.  So we start with a formula B with m clauses and n variables.  We’ll write some functions:

AssignXi(c1..cm): generates two calls to AssignXi+1. The function has one parameter for each clause.  The first call simulates setting variable Xi to true by passing a “true” value in all parameters that represent clauses that have variable Xi represented positively.  The second call simulates setting variable Xi to false by passing a “true” value in all parameters that represent clauses that have variable Xi returning negatively.  In all other cases, the function passes on the ci parameter it was given.

AssignXn(c1..cm): once we reach the end of the variables, we have to stop.  This function calls the “Check” function we’ll be defining in a minute twice, once reflecting setting variable Xn to true, one reflecting setting it to false.

Truej(cj+1..cm):There is one “true” function for each clause, each one has a parameter for all clauses with larger numbers. The paper writes this function a little weirdly, but I think a good definition is:

if(cj+1 is true){
Truej+1(cj+2..cm);
else
Falsej+1(cj+2...cm);
}

So, as long as the parameters are true, we’ll continue calling down through the  true functions to the end.  The last True function is what will make us formally recursive:

Truem(): Calls Assign1(False, False, ...False). Our main program will begin with a call to Assign1 with these exact parameters, so if we can get here, we will have found our recursive call.

The False functions end a call chain:

Falsej(cj+1..cm){
// do nothing
}

The Check function’s job is to start the appropriate call to True or False:

Check(c1..cm){
if(c1 is true)
True1(c2..cm);
else
False1(c2..cm);
}

Our main program is just a call to Assign1(False, False..False).  It’ll go through all of the various AssignXifuntions trying to assign variables (and thus clauses) to true. Each assignment will be checked, and each check will either hit a False function (meaning a clause wasn’t satisfied, and so we will backtrack and try an alternate assignment) or the final True function, which will generate our recursive call.  So this program has a recursive call chain if and only if the formula was satisfiable.

Notice that while the run of this program might take exponential time, that’s ok because reductions are concerned with the time it takes to create the new problem instance, and there are “just” 2m+n+1 functions to create.

Difficulty: 6.  This is a neat problem and reduction- I think the “write a backtracking program to try all combinations” is pretty gettable.  The hard part is the check and true/false functions at the end.  We can’t really use loops because loops make programs undecidable (you can’t show the problem is in NP by going down d+1 calls if you might have an infinite loop someplace and won’t get through all of those calls).  So we have to build a chain of recursive calls instead, with dead-ends to force the backtracking.

Protected: Non-Containment for Free B-Schemes

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

Protected: Inequivalence of Loop Programs Without Nesting

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

Protected: Inequivalence of Programs with Arrays, Inequivalence of Programs with Assignments

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

Protected: Code Generation With Unfixed Variable Locations

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: Tree Transducer Language Membership

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: Regular Expression Inequivalence on Single Character Alphabets

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