Category Archives: Appendix: Miscellaneous

Maximum Likelihood Ranking

Posted on October 27, 2023 | Leave a comment

This is another (hopefully the last, we’re getting close to the end) “private communication” problem where I couldn’t find a paper to use, so I had to work through it myself, with mixed success.  Let’s see how I do.

The problem: Maximum Likelihood Ranking.  This is problem MS11 in the appendix.

The description: Suppose we have an nxn matrix A with integer values.  Further, let aij + aji = 0.  We’re also given a positive integer B.  Can we do “simultaneous row and column permutations” to A to create another matrix (G&J call it B, but I’ll call it C to avoid confusion), such that:

\sum_{1 \leq i < j \leq n} min\{b_{ij},0\} \geq -B?

The description (my interpretation): Here’s what I think that means.  You have a directed  graph with just one edge in each direction between any 2 vertices, represented as an adjacency matrix  A positive entry in the matrix is the cost to traverse the edge, and a negative entry in the matrix means you’re traversing the edge backwards.  Can I permute the rows and columns of the matrix so that the “backwards” edges in all positions where i < j sum to -B at most?”

Example: Here is a graph:

Here is its matrix:

\begin{bmatrix} 0&1&0&5&7 \\ -1&0&3&-2&0\\ 0&-3&0&4&0\\ -5&2&-4&0&6\\ 7&0&0&6&0\\ \end{bmatrix}

The negative numbers in the upper right triangle is what we are looking at to compare against our B- in this case it’s -9.

I’m pretty sure a “simultaneous row and column permutation” means you do the same permutation to the rows and to the columns.  So if the above matrix was {1,2,3,4,5}, here is {2,3,4,5,1}

\begin{bmatrix} 0&3&-2&0&-1\\ -3&0&4&0&0 \\ 2&-4&0&6&-5 \\ 0&0&-6&0&7\\ 1&0&5&-7&0\\ \end{bmatrix}

The negatives in the upper right triangle here sum to -8 (so it’s better).  It’s worth noticing that we have two cycles in the graph (2->3->4->2 and 1->4->5->1), and that any permutation will have to have a “backwards” ordering for one of the cycles.  So at least 1 edge in each cycle will have its negative value counted in our total, so this graph will be at least -7.

(Partial) Reduction: As I said, this is a “private communication” reduction, our only hint is that we are supposed to use Feedback Arc Set.  What Feedback Arc Set asks for is a set of edges that is in each directed cycle.

So, let’s try this:  Given a directed graph G=(V,E) that’s our Feedback Arc Set graph, represent it as an adjacency matrix such that aij = 1 if edge (i,j) is in E, and aij = -1 if (j,i) is in E.  Our B will be the K from the problem.

My intuition is that each cycle will have to contribute 1 edge (at least) that is negative in our upper triangle.  So if there are K edges that cover all cycles, we would get the B cost from those edges in our problem.  We want the edge in the feedback arc set to be last in the permutation order.  For example, here is a directed graph:

Here is its graph with the regular ordering:

\begin {bmatrix} 0&-1&1&-1\\ 1&0&-1&0\\ -1&1&0&0\\ 1&0&0&0\\ \end{bmatrix}

..for a cost of -3.  But we can solve the FBS instance with just 1 edge from 1-3.  So here is the matrix will all edges going forward except for that one (3,2,4,1 ordering):

\begin{bmatrix} 0&1&1&-1\\ -1&0&0&1\\ -1&0&0&0\\ 1&-1&0&0\\ \end{bmatrix}

..for a cost of -1 (because there is just 1 edge in the Feedback Arc Set)

I’d like to have my reduction be someting like “put all edges in the Feedback Arc Set in the matrix in order where they go backwards”.  But I don’t know what to do with graphs like this, where the Feedback Arc Set itself is a cycle, so you can’t do that:

{(3,4), (4,6), (6,3)} is the Feedback Arc Set here, but because it is itself a cycle, there is no permutation of vertices that will put all of the edges in the upper right.  I think this is a consequence of there being 4 cycles in the graph, but the Feedback Arc Set having just 3 edges.  But I’m not sure, and so we need to have something more in the reduction.

Difficulty: ??  It doesn’t look terribly hard, but I’m not sure what to do next.

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , , ,

Randomization Test For Matched Pairs

Posted on October 13, 2023 | Leave a comment

This reduction gave me a lot of trouble and gave me a lot of holes to fill.  I think I filled them okay, but I’m getting the vibe that I’m missing something here- the reduction reads very differently from the way the problem is described.

The problem: Randomization Test For Matched Pairs.  This is problem MS10 in the appendix.

The description: Given a series of n pairs of integers (x1, y1) through (xn, yn), and a positive integer K.  Are there at least K subsets of the integers for which:

\sum_{i \in S} |x_i - y_i | \leq \sum_{y_i > x_i} (y_i - x_i)?

Example:  The paper by Shamos that has the reduction might have a better explanation of what we are doing: he defines zi = yi – xi, and T* to be the sum of all of the positive zi (the right side of the inequality above).  Then if we could choose some set of zi to be positive (by changing their sign), and call that sum T, are there K or more sets where T \leq T*?

So, suppose we have 4 pairs: (2,4), (1,6), (8,4), (3,2).  This would make our zi‘s {2,5,-4,-1}, and so T* would be 7.

There are 16 subsets of the above pairs (nothing seems to say that the empty set isn’t allowed).  Here are some whose T is \leq 7:

{(2,4), (1,6)}   (T=7)

{(2,4), (8,4)} (T=6)

{(2,4), (8,4), (3,2)} (T=7)

{(3,2)} (T=1)

..and so on.  A set that does not work is {(1,6), (8,4)} since its T is 9.

Reduction: Shamos uses Partition, so we are given a set of N elements.  The total sum of the elements is S, so we want two subsets of size S/2. He wants to “Perform the randomization test on the numbers” in the partition set, which I don’t get because the test needs to be done on pairs.  He also wants T* to be S/2.  The paper seems to say that you can just set that, but it has to be based on the zi.  So I came up with a way to make that happen:

For each item xi, create a pair  (xi, 0).  The zi for each of these elements will be negative.  Then add one extra pair (0. S/2).  Since this is the only positive z value, T* will be this value.  I don’t know if this is what the paper wants me to do, and I’m a little worried that adding an extra element will throw off what is next.

The paper then claims that if there is no partition of the set elements into equal-weight subsets, there are 2N-1 subsets with a T < T*.  This is because if there is no partition of equal size, then each subset of our elements either has a sum < S/2 (and this a T < T*), or its complement does.

If there is a partition, then 2 sets will have a T value of exactly T* (the two partition subsets) and half of the remaining subsets will have a T < T* as above.  So if we set K (the number of subsets whose T needs to be <= T*) to be 2N-1+2, we will have our reduction.

Difficulty: 7. I spent a long time trying to read and understand this reduction.  It’s very sparse, and, really, doesn’t explain at all how to make the pairs.  As a result, I’m pretty sure I filled in all of the holes, but it’s very possible that I’m missing something.

 

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , , ,

Clustering

Posted on September 29, 2023 | Leave a comment

I feel a little silly I didn’t come up with this one myself.

The problem: Clustering.  This is problem MS9 in the appendix.

The description: Given a complete weighted graph G=(V,E), with a positive weight d(i,j) for each edge eij, and two positive integers K and B.  Can we partition V into K (or less) disjoint sets V1..Vk such that within each Vi, all edges that stay within the partition cost B or less?

Example: Here is a graph:

If K=2, and B=2, we could have the sets {A,C} and {B,D} as a legal cluster.  But if  K=2 and B=1, we will not be able to solve the problem.  For example, we might want to have the edges (A,B) and (A,D) in the same cluster, but that would require us also to consider the edge (B,D), which is larger than 1.

Reduction: Brucker’s paper introduces the problem using a graph, like I did above. (G&J talk about points and distances), His reduction is from Graph Coloring.

Suppose we have a coloring graph G.  We build a new graph G’ such that the weight of an edge in G’ is 1 if it did not appear in G, and its weight is 2 if it did appear in G.  Then we set out K = the K of the coloring problem (3 for 3-coloring), and B = 2.  A partition of the vertices into 3 sets where each set has no weight-2 edges is exactly a legal coloring.

Difficulty: 3.  I do think the graph terminology helps to make the problem more understandable.

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , ,

Shapley-Shubik Voting Power

Posted on September 15, 2023 | Leave a comment

Setting up this definition will take a bit, bear with me.

The problem: Shapley-Shubik Voting Power.  This is problem MS8 in the appendix.

The description: Suppose we have a set of n voters, each voter i has a “weight” wi, corresponding to their number of votes.  If we are doing a simple majority vote, a coalition of voters then needs votes of (strictly) more than half the sum of the weights to win.  For a specific voter i, we can look at all permutations of voters, and say that all voters before voter i in the permutation voted “yes”, and all voters after voter i in the permutation voted “no”.  We are interested in the number of these permutations where voter i’s vote “matters”- where adding voter i to the “yes” votes makes “yes” the majority, but adding them to the “no” votes makes “no” the majority.  We call voter i a pivot player if this is the case.

Is voter 1 (in the G&J definition, it’s voter N in the paper) ever a pivot?

Some clarifications:  The number of times a voter is a pivot is the “Shapley-Shubik voting power”, and the proportion of permutations the voter is a pivot (by dividing the count by N!) is the “Shapley-Shubik power index”, but all we care about here is whether the power is non-zero.

Also, the definition of the voting game (in G&J, and also in the paper) allows for a more general definition of winning, besides a simple majority- you can supply a “quota” q, and any amount of votes ≥ q is a winning coalition.  For us, q is set in the reduction to be 1/2 the sum of the weights, +1, rounded up.

Example: Suppose we had 4 voters, with weights: 5.4,3,1.  There is 13 total weight, and 7 weight is enough to win. Voter 4 has 0 coalitions in which they are the pivot (we would need 6 votes without them), so has “zero Shapley-Shubik voting power”.

If, however, we split up the same number of votes among 5 voters: 4,3,3,2,1, then the 1-vote voter can be a pivot with (among others) the 4 and the 2.  The coalition loses without our pivot voter but wins with them.

Reduction: G&J have this as an “unpublished results” problem, but luckily I found a paper by Matsui and Matsui who solved it.  So we start with Partition.  We’re given a set A of n integers.  We will create a set of weights with one weight equal to each element of A, and add one extra voter with weight 1 at the end.  This is the voter that may or may not be a pivot.

If this last voter is a pivot, then there is a coalition that needs an additional weight of 1 to become a majority.  This means the coalition had exactly half of the votes without this voter (and so the sum of the elements is a partition of A)

In the other direction, if the set has a partition, then the partition set’s votes is equal to exactly half of the votes, one short of a majority.  Adding our 1-weight voter will make it a majority, and thus that voter is a pivot.

Difficulty: 4.  This problem looks scary because the definitions of Shapley-Shubik voting power include a lot more than what you actually need to do this reduction.  Once you get past all of that, it’s actually a pretty nice problem that students can handle.

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , ,

Decoding of Linear Codes

Posted on September 1, 2023 | Leave a comment

I think I can get through the rest of the appendix this semester.  Fingers crossed.

The problem: Decoding of Linear Codes.  This is problem MS7 in the appendix.

The description: We are given an NxM boolean matrix A, a vector y with m 0’s and 1’s in it, and an integer K.  Does there exist a boolean vector x, with n elements, and at most K 1’s, where for each column j:

\sum_{i=1}^{n} x_i*a_j \equiv y_j (mod\, 2)?

Example: Here is a matrix A:

\begin {bmatrix} 0&1&0&1 \\ 1&0&1&1 \\ 0&1&1&1 \end {bmatrix}

If our vector y is (1,0,0,1), we are saying we want a vector x that is different from the first and fourth column of A in one (or 3) positions and is different from the second and third column in 0 (or 2) positions.   A vector such as (0,1,1) will do this.

If y was (1,1,1,1), I don’t think it’s possible to come up with any vector x, because since the first two columns of A are opposites, any vector that differs in the first column in 1 (or 3) positions will differ in the second column in 2 (or 0) positions, so we won’t be able to satisfy both elements of y simultaneously.

Reduction:

The paper by Berlekamp, McEliece, and van Tilborg calls this the  “Coset Weights” problem, and uses 3DM, adding the assumption that all 3 dimensions come from the same set of parent elements. So we start with a set U (they call it “W” in the paper) of triples.

We will use these triples to build our matrix A.  Our matrix will have one row for each triple and 3 columns for each element in our parent set (so 3q columns total).  We then build an incidence matrix of each of our triples- each row will have exactly three 1’s in it, corresponding to the element in each of the three dimensions it is.  So, for example, if the sets we are making our triples from were all {1,2,3,4}, and our triple was (1,2,3), the row for that triple would be {1,0,0,0, 0,1,0,0,0,0,1,0}

We’ll choose y to be a vector of all 1’s.  Now we are looking for a vector x of 0’s and 1’s.  This will be like choosing triples from the 3DM instance.  (A 1 in the vector means we choose that row and a 0 means we don’t).  We’ll set K=q to make sure that we choose exactly q triples.

So, a set of q triples that covers all elements will have a 1 in each column in one of these triples and give us a solution to our problem. Similarly, a vector with q 1’s in the correct places that covers all columns will generate our y vector.

Difficulty: 5.  Matrix manipulation is something I personally don’t feel terribly comfortable with, but this is a pretty straightforward implementation of it.

 

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , ,

Permutation Generation

Posted on August 18, 2023 | Leave a comment

I think this is a problem we’ve done before.  Let’s see if I’m right.

The problem: Permutation Generation.  This is problem MS6 in the Appendix.

The description: Given a set F of functions on some set A (each f in F maps from A to A), and a “goal” function h, also from A to A.  Can we get h from some composition of the functions in F?

Example: Suppose F was:

  • f1(x) = x+1
  • f1(x) = 2x
  • f3(x) = x+2

with all functions mapping from Z->Z.  If h was the function x+3, we could get it by h(x) = f1(f2(x)).  We could not get the function x+7 out of any composition of the above functions.

Reduction: G&J send us to the paper by Garey, Johnson, Miller and Papadimitriou we used for Arc Coloring.  In that problem we had a detour into the “Word Problem For Products of Symmetric Groups” (WPPSG), which I think is this problem, or at least a version we can reduce from for our problem.

WPPSG asks: Given a set X of permutations on the numbers 1..K and a “goal” permutation π, can π be written as a composition of the permutations in X?

We can view a permutation of 1..K as a function, then our h is just the permutation π: h(1) = the first element of π, h(2) = the second element of π, and so on. Thus, we have a function composition that reaches h if and only if we have a combination of permutations that reach π.

Difficulty: 4, if you’ve seen the WPPSG problem.  It’s easy for people to get confused about the difference between functions and sequences here.

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , , ,

Finite Function Generation

Posted on March 17, 2023 | Leave a comment

We’re moving away from the Perti Net stuff to a simpler problem to describe, though the reduction is pretty convoluted.

The problem: Finite Function Generation.  This is problem MS5 in the appendix.

The description: Given a set of functions F whose domains and co-domains are the same finite set A, and a new function h, also from A->A.  Can h be created by composing functions from F?

Example: Here’s a pretty simple example.  Let A = {0,1,2,3,4,5}

Let F consist of 2 functions:  F2(x) = (x+2) mod 6, and F3(X) = (x+3) mod 6

If h is h(x) = (x+1) mod 6, we can get it from F2(F2(F3(x))).

But if we replace F3 with F4 (X) = (x+4) mod 6, then we can never make h, because all combinations of F2 and F4 keep the same odd/even parity of the inputs.

Reduction: Kozen, who has the paper with the reduction on Finite Automata Intersection, uses that problem here as the basis for his reductions.  G&J say that the reduction is from Finite Automata Intersection, but since the finite automata we use are the ones created in that reduction, I think it’s more correct to say that this reduction is from LBA Acceptance, since that is where we start with an arbitrary problem instance.

The Finite Automata Intersection reduction started with an arbitrary machine M and an input string w, and made a bunch of finite automata Fi such that M accepts w if and only if there was at least one string in the language of each F1 (i.e., the intersection of the languages of the machines is non-empty). We’ll label state j of machine i qij.  Because they are FA’s, each machine i has one start state (qistart ), and they were built to have one final state (qifinal).

Create a set A which will be the set of the states of all machines, plus three extra elements: o1, o2, and o3.  Every symbol in the common alphabet of the machines a gets a function fa:

  • fa(qjj ) = The state we go to from qij on input a.  Note that this will be some qik for some k (some state on the same machine).
  • fa(o1) = o3
  • fa(o2) = o2
  • fa(o3) = o3

It’s worth mentioning that since the machines are DFAs, there is a well-defined transition from each state on each input symbol, so these are functions that provide a single value for each domain element.  Also notice that we can compose these functions to build fw for some string w: fw(q) = the state we end up in starting in state q on the string w.  This means that a machine i accepts a string w iff fw(qistart ) = qifinal.

We’ll add a new function “finit” to our set of functions.  finit takes elements from A:

  • f(q) returns qistart if q is any state in a machine qi
  • f(o1) = o2
  • f(o2) = o3
  • f(o3) = o3

Now we’ll build our function h:

  • h(q) returns qifinal if q is any state in a machine qi
  • h(oi) = finit(oi) for i from 1 to 3.

Suppose that there is a string w in the languages of all of our automata Fi.  This would mean that for all machines i, fw(qistart ) = qifinal.  It also means that those f functions need to map fw(o1) to o3, fw(o2) to o2, and fw(o3) to o3.  We can get this by h = fw ° finit.

In the other direction, suppose we can generate h by the composition of our f functions.  The first function in the composition has to be finit because all other functions take o1 to o3, and then all functions keep o3 at o3.  This can’t happen because h(o1) = o2.

After the first finit, we can’t have another finiit because calling finit twice would take o1 to o2 the first time, and then to o3 the second time.  All of the other fa functions keep o2 at o2.  So we know the composition has to be finit first, then some number of f1 functions forming a composed fw.

If h is given any state in a machine as input, it returns the final state of that machine.  If finit is given any state in a machine as input, it returns the start state of that machine.  For fw(finit(q)) to return qifinal, it must be the case that fw(qistart) = qifinal, for all i.  This gives us a string w that is in the language of each machine.

Difficulty: 8.  It’s interesting to see how the functions are made- that there is a function for each input symbol, instead of for each machine, which I, at least, would expect.  Also, the use of the various oi inputs is important, easy to mess up, and hard to come up with.

 

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , , ,

Reachability for 1-Conservative Petri Nets

Posted on January 27, 2023 | Leave a comment

As promised, here is the next problem, also using Petri nets.  I’m not 100% convinced that my definition of “1-Conservative” is accurate, but it seems to work for this reduction.

The problem: Reachability for 1-Conservative Petri nets.  This is problem MS4 in the appendix.

The description: A “1-Conservative” Petri net has each transition preserve the number of tokens on each side of the transition, and has at most 1 token per edge.  Given such a Petri net and a state M, is there a sequence of transitions that can reach M from the starting state?

Example: I had a hard time finding a non-trivial example of a 1-conservative network.  But maybe that’s ok.  Here’s another figure from the Murata paper:

There are no tokens in this picture.  But notice that if we start with no tokens, no state with tokens is reachable.  If we start with a token in the left state, then both 1-token configurations are reachable, but we won’t be able to reach a configuration with 0 tokens or 2 tokens in it.

Reduction: This is Theorem 3.1 in the Jones, Landweber, and Lien paper.  The reduction is from Linear Bounded Automaton Acceptance.

So we start with a LBA M, with p tape symbols, and m states.  It has an input string $x1x2..xn$.  Our task is to build a 1-Conservative Petri Net.

The first set of places in the Petri net will be represented by Aij,  0 <= i <= n+1, 1 <= j <= p.  This will represent the tape.  Aij will have a token iff space i of the tape has symbol j.

We will also have places labeled Qij, 0 <= i <= n+1, 1 <= j <= m.  This will simulate the states.  Qij will have a token iff the head is over space i of the tape while the machine is in state j.

We’ll also have 2 special places C and D.  Tokens start in all of the Aij places corresponding to the input string of the tape, and in Q11 (the machine starts in state 1 over cell 1 of the tape).

The transitions in the net are based on the transitions in the machine.  If we have a transition from state qs and symbol at to state qr, writing a symbol al we add a transition Qis + Ait -> Qjr + Ail for all i.  “j” in the destination is either i, i+1, or i-1, depending on if the head stays, moves right, or moves left.

If we are in a final state qs, we add a transition Qis->C for all i.

We also add the transition C+Aij -> C+D.

Note that all transitions have 1 token per edge and preserve the number of tokens, so this is a 1-Conservative Petri net.

Our destination state is:

  • 1 token in C
  • N tokens in D
  • 1 token in each Ai1

Since all of these transitions simulate the movement in the LBA, if the LBA accepts the string, we follow all of the transitions to eventually put the token in C.  This allows us to do the last transition to put the tokens in D.

In the other direction, if we can reach the desired state, we must have put a token in C.  To get there, we must have gotten to a final state qf.  Thus, the LBA must have accepted the string (by following the transitions we took in the Petri Net to get to that qf state).

Difficulty:  7.  I like how they can represent all combinations of tape symbols and locations as places.  I’m a little worried because it looks like this assumes you’ll never go beyond the end of the input string, where I thought an LBA was allowed to use a linear multiple of the input string’s size.  Is there some kind of equivalence proof that says an LBA can only need its own input string’s space exactly?

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , ,

Non-Liveness of Free Choice Petri Nets

Posted on January 12, 2023 | Leave a comment

The next couple of problems talk about “Petri Nets”, which I hadn’t heard of before.  I found a decent explanation here, and the Wikipedia article also has a good explanation, though I found it pretty dense.  I also took some definitions from a nicely explained paper by Murata.

The problem: Non-liveness of Free Choice Petri Nets.  This is problem MS3 in the appendix.

The description: Given a Petri Net, with the “free choice” property (which means every “place” node either goes to one transition or has input from 1 transition), is it not live? A Petri Net is live if, after any sequence of transitions, each transition remains potentially firable by some future sequence of transitions.   So we are asking- is there a set of transitions that will create a situation where at least one transition will no longer be able to fire?

Example: Here is a live Petri Net from Murata’s paper:

Notice how whatever sequence of transitions we do from the initial state, we will be able to “reset” the net and get to any transition.

Notice that this net is also not “Free choice”, because place P1 gets inputs from 2 transitions, and also feeds into 2 transitions (The 10¢ and 25¢ places also violate this property)

Here is a non-live one from the same paper:

This is not live because even though every transition is reachable from the start state, if we choose the t1 transition to start, we will not be able to ever fire t4.  (In fact, we won’t be able to fire any other transitions).

Also notice that this second Net does have the Free choice property, since each circle has either indegree or outdegree 1 (or both).

Reduction: The reduction is in the paper by Jones, Landweber, and Lien, and it reduces from CNF-SAT. So we start with a formula that has n variables and k clauses.  The Petri Net we build has three places for each variable xi:

  • A place xi associated with the positive setting of the variable
  • A place ~xi associated with the negative setting of the variable,
  • A third place Ai, which will be used to link the two.

For each literal li in clause Cj, we have a place associated with the negation of the literal in the clause (the setting that does not make the clause true).  So, for example, if xi was in clause Cj, we’d have a place (~xi, Cj)

We will also have one last place “F”, which will mean the formula is not true (because some clause was not true)

Our net will have 1 token for each variable, starting in the “A” places, one for each variable.

We will have transitions between:

  • Each Ai and its xi and ~xi
  • Each xi and all of the places corresponding to literals that hold the negation of that variable.  So a transition between xi and places like (~xi, Cj)
  • A transition straight to F for each clause if all of the “literal” places for a clause have tokens.
  • A transition from F to each Ai

The idea here is that the places for literals will gather tokens if their variables are set in a way to not make the clause true.  If none of the literals in the clause are set to make the clause true, then the clause is false, all of their places will have a token, and F will fire.  F will then enable the firing of all of the A places, and we will go around again.

So, let’s suppose the formula is satisfiable.  The tokens start in each Ai, which has transitions to xi and ~xi.  Pick the transition that corresponds to how we set xi in the satisfying assignment of the formula. This will enable some transitions in clauses with xi in it to fire- the literals that have the opposite settings of the variable.  But since every clause is satisfiable, there will not be enough firings to enable the transition to F to fire, and the net will be dead (no more firings will happen after those).

On the other hand, if the formula is not satisfiable, then all assignments of variables make at least one clause false.  So no matter how we decide to make the Ai transition go (to the xi or to the ~xi), some clause will not be satisfied, and that clause will be able to fire its transition to F.  Firing F puts a token at each Ai, enabling all transitions to start again.

Difficulty: 6.  Obviously, this only works if you’ve discussed Petri Nets previously, since learning about them is a separate involved discussion.  But outside of that, the idea of a transition firing on a clause being false is a pretty cool one, and makes sense, because we are looking for non- liveliness, so a Satisfiable formula means we want dead transitions.

Also, I want to commend the Jones, Landweber, and Lien paper for having a very nice example explaining how a formula turns into a Petri Net complete with transitions and explanations working through how what fires and why.  I don’t get that in every paper, and it was nice of them to think about people like me coming along 45 years later.

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , , ,

Cyclic Ordering

Posted on December 21, 2022 | Leave a comment

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 (αi,γi, β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.

Leave a comment

Posted in Appendix: Miscellaneous

Tagged , ,