Tag Archives: Difficulty 7

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 (x₁, y₁) through (x_n, y_n), 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 z_i = y_i – x_i, and T* to be the sum of all of the positive z_i (the right side of the inequality above). Then if we could choose some set of z_i 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 z_i‘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 z_i. So I came up with a way to make that happen:

For each item x_i, create a pair (x_i, 0). The z_i 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 2^N-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 2^N-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.

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 $x₁x₂..x_n$. Our task is to build a 1-Conservative Petri Net.

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

We will also have places labeled Q_ij, 0 <= i <= n+1, 1 <= j <= m. This will simulate the states. Q_ij 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 A_ij places corresponding to the input string of the tape, and in Q₁₁ (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 q_s and symbol a_t to state q_r, writing a symbol a_l we add a transition Q_is + A_it -> Q_jr + A_il 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 q_s, we add a transition Q_is->C for all i.

We also add the transition C+A_ij -> 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 A_i1

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 q_f. Thus, the LBA must have accepted the string (by following the transitions we took in the Petri Net to get to that q_f 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?

Betweenness

Posted on December 7, 2022 | Leave a comment

The last section is on “Miscellaneous” problems. There are some weird ones in here, but we start with a pretty straightforward number problem.

The problem: Betweenness. This is problem MS1 in the appendix.

The description: Given a set C of triples (a,b,c), where each element of each triple comes from a superset A, can we find an ordering of the elements of A such that according to that ordering, each triple is in either increasing or decreasing order?

Example: It’s actually hard to do a good example for this because most groups of symbols (digits, letters, subscripts, …) have an implicit ordering of elements, and to go against that would be confusing. Having random symbols without connotations of meaning gets pretty confusing pretty quickly as well.

So let’s lean in and say A = {a,b,c,d,e,f} and our triples are:

(a,d,f)
(f,d,b)
(h,d,a)
(f,g,h)
(d,f,h)

We’re allowed any ordering of the elements of A, and the “normal” lexicographical one with ‘a’ first and ‘f’ last satisfies the betweenness rules.

But now suppose we add the new triple: (b,a,d). That is an illegal triple in our normal order, but if we change our ordering so that ‘b’ is first and ‘a’ is second, we can still satisfy all of the triples.

Reduction: The paper by Opatrny uses Hypergraph 2-Colorability (which we called “Set Splitting”). Recall that our reduction only made sets of size 3, so we can start with an instance where each set has at most 3 elements (or, each hyperedge connects at most 3 vertices).

So, suppose we have a set of N vertices s₁..s_n, a set of J 3-vertex hyperedges (a_i, b_i, c_i), as well as M 2-vertex “regular” edges (d_i, e_i).

Our first job is to build superset A. It has:

One symbol for each vertex,
A new symbol X.
A set of J new symbols Y_k, one for each 3-vertex hyperedge.

Now we build C.

Each hyperedge (a_k, b_k, c_k) generates two triples: (a_k, Y_k, b_k) and (Y_k, X, c_k)
Each two-vertex edge (d_k, e_k) generates the triple (d_k, X, e_k)

Suppose the graph had a 2-coloring. Recall that meant that each vertex had a color (the paper uses red and blue) so that each edge and hyperedge touches vertices of both colors. We need to make an ordering of A that satisfies all triples. The ordering will have positive, negative, and rational ranks.

X has rank of 0.
If vertex s_i is red, its rank is i. If it’s blue, its rank is -i.
Each Y_i was associated with a hyperedge (a_i, b_i, c_i).
- If a_i and b_i have the same color (and so the same sign), Y_i‘s rank is min(rank(a_i), rank(b_i)) + $\frac{1}{i+1}$ .
- If they have different colors, the rank is $\frac{1}{i+1}$ if c_i is blue, and $-\frac{1}{i+1}$ if c_i is red

So, suppose every edge had 2 colors. We know:

If a_i and b_i are the same color, they are the same sign, and Y_i is between them, satisfying the (a_k, Y_k, b_k) triple.
If a_i and b_i are the same color, c_i must be the other color (and the other sign from Y_i), satisfying the (Y_k, X, c_k) triple.
If a_i and b_i are different colors, they are different signs. Setting Y_i to a value between 1 and -1 satisfies the (a_k, Y_k, b_k) triple.
If a_i and b_i are different colors, c_i can be either color, so making Y_i the opposite sign as c_i satisfies the (Y_k, X, c_k) triple.
An edge with just 2 vertices needs both vertices opposite colors, and thus opposite signs, so the (d_k, X, e_k) triple is satisfied.

So far, so good. In the opposite direction, suppose we have a solution to the betweenness instance. We’ll assign colors to vertices such that a vertex’s color is red if its rank is > X’s rank. Otherwise, it will be assigned blue. Our triples will now allow any set of a_i, b_i, and c_i to all be greater than or less than X (or for both d_i and e_i to be greater than or less than X), which means that every edge in the hypergraph has both a red and a blue vertex.

Difficulty: 7. It’s relatively easy to see what you need to do. It’s harder to make the numbers actually work. Even this paper has to resort to using rational numbers for the ranks, which is a fixable problem, but certainly not obvious.