Tag Archives: Difficulty 7

Simultaneous Divisibility of Linear Polynomials

Sorry for missing last week- my grading backlog is getting out of hand.

The problem: Simultaneous Divisibility of Linear Polynomials.  This is problem AN3 in the appendix.

The description: Given two sets A and B, each containing n vectors, each vector having m+1 integer entries (so for example, vector ai has values ai[0] through ai[m]) , can we find m positive integers x1 through xm such that for each pair of vectors ai and bi,

(ai[0] + ai[1]*x1 + ai[2]*x2+…+ai[m]*xm) divides (bi[0] + bi[1]*x1 + bi[2]*x2+…+bi[m]*xm)

Example: Suppose a1 was (1,2,3), b1 was (2,4,6), a2 was (4,2,4), and b2 was (7,9,10).  Then if I pick x1 = 3, x2 = 2, a1‘s equation evaluates to 13 and b1‘s evaluates to 26.   a2‘s equation evaluates to 18, and b2‘s equation evaluates to 54.  Since both a values divide their corresponding b values, we have found an x1 and x2 that work.

Reduction: The paper I found by Lipschitz that has the reduction reduces from Quadratic Congruences.  He starts by assuming that m ≤ 2n because at most 2n of the ai and bi are independent (and so the extra variables can be made equivalent to the first 2n variables by transformation).    He also uses a variation of Quadratic Congruences that states the problem is still NP-Complete if c ≤ b/2.  Then given a,b, and c, we build our divisibility problem with 5 formulas over the variables x, y, u, and v:

  • x+u | c+1
  • 4y + v | b2-1
  • x+b | y-b2
  • x+b+1 | y-(b+1)2
  • b | y-a

It turns out that if we can find an x such that x2 ≡ a mod b if and only if we can find x,y,u, and v to satisfy those divisibility problems.

If we can solve the quadratic congruence, then setting y=x2, u = c-x+1 and v = b2 – 4x2 + 1 satisfies all of the divisibility equations.

In the other direction, if we have found x,y,u, and v that works, we know:

  • x ≤ c (which is ≤ b/2) from the first equation
  • y ≤ b2/4 from the second equation
  • y = x2 + k(x+b)*(x+b+1) for some k ≥ 0 from the 3rd and 4th equations

Suppose k is not 0, and thus y is not equal to x2.  Then y has to be > b2, which violates the second fact above.  So k is really 0 and y=x2.  Then the last equation is a restatement of the quadratic congruence problem, and y (=x2 ) is congruent to a mod b.

Difficulty: 7.  I think the way this all works out is very slick, and I like how the equations give you the answer, but I have no idea how you’d come up with these equations on your own.

Simultaneous Incongruences

Back to the problems we’ve skipped over, starting with a cool take on the classic “Chinese Remainder Theorem”.

The problem: Simultaneous Incongruences.  This is problem AN2 in the appendix.

The description: Given n pairs of positive integers (a1, b1)…(an, bn), can we find an integer x such that x \not\equiv ai mod bi?

(G&J also add the rule that  ai ≤ bi for all i, but we can easily make that happen by doing division)

Example: I think it’s easier to see this as the actual congruences:

Can we find an x such that:

  • x \not\equiv 1 mod 2
  • x \not\equiv 2 mod 3, and
  • x \not\equiv 3 mod 4?

If we chose x as 4, we’ll see that it works.  For a simple example of a case that fails, we can do:

  • x \not\equiv 1 mod 3
  • x \not\equiv 2 mod 3, and
  • x \not\equiv 3 mod 3

Reduction: I found this reduction in the Algorithmic Number Theory book by Bach and Shallit.  Their Theorem 5.5.7 calls this the “Anti-Chinese Remainder theorem”.  They reduce from 3SAT.

Our formula will have t variables and each clause in our formula is made up of 3 literals, which we’ll represent as Ci = (zai∨zbi∨zci).  For each ai find pai, the aith prime number, and find pbi and pci similarly.  Define ai‘ to be 0 if zai is a positive literal, and 1 if it’s a negative literal, and define bi‘ and ci‘ similarly.   Now for each clause, use the regular Chinese Remainder theorem to find a value xi where:

  • xi \equiv ai‘ mod pai
  • xi \equiv bi‘ mod pbi
  • xi \equiv ci‘ mod pci

Our system of incongruences will be:

  • x \not\equiv 2 (mod 3)
  • x \not\equiv 2,3 (mod 5)
  • x \not\equiv 2,3,4,…pt (mod pi)   (pt is the tth prime number)

The above incongruences are there to force x to be 0 or 1 mod each pi. I think these correspond to true-false values to the variables in the SAT instance (x being 0 mod pi means setting that variable false, making it 1 mod pi means setting that variable true)

  • x \not\equiv xi (mod pai*pbi*pci) for each i

This turns out to be O(n+t3) incongruences by the Prime Number Theorem.

Each clause in the SAT instance is satisfiable unless all 3 literals are false.  By the way we’ve created our ai‘  (and b and c), this means that the variables can’t be set to be equal to all of ai‘, bi‘ and ci‘.  Because of how our xi was chosen, this means that x is not congruent to xi (mod pai*pbi*pci).

Difficulty: 7.  This is a cool short reduction, but the way the x value works is something you don’t usually see.

Protected: Integer Knapsack

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

Protected: Resource Constrained Scheduling

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

Protected: Single Execution Time Scheduling With Variable Number of Processors

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

Protected: Sequencing With Deadlines and Setup Times

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

Serializability of Database Histories

This is another problem with a cool elegant reduction once you get past the baggage you need to know to understand the problem.  This database section seems to be full of problems like these.

The problem: Serializability of Database Histories.  This is problem SR33 in the appendix.

The description: We have a set V of variables in our database, and a set T of transactions, where each transaction i has a read operation (Ri) that reads some subset of V, and a write operation Wi that writes some (possibly different) subset of V.  We’re also given a “history” H of T, which permutes the order of all reads and writes maintaining the property that for all i, Ri comes before Wi in the history.  Think of this as a set of parallel transactions that reach a central database.  H is the order the database processes these operations.

Can we find a serial history H’ of T, with the following properties:

  • Each Ri occurs immediately before its corresponding Wi.
  • A “live transaction” is a transaction (Ri, Wi) where either Wi is the last time a variable is written before the Rj of some other live transaction or the last time the variable is written at all.  The set of live transactions in H and H’ needs to be the same.
  • For each pair of live transactions (Ri, Wi) and (Rj, Wj), for any variable v in Wi∩Rj, Wi is the last write set to contain v before Rj in H if and only if Wi is the last write set to contain v before Rj in H’.  The paper says that this means transaction j “reads from” (or “reads v from”) transaction i.

Example: The paper by Papadimitriou, Bernstein, and Rothnie that has the reduction has a good simple example of a non-serializable history:

H= <R1, R2, W2, W1>, where R1 and W2 access a variable x, and R2 and W1 access a variable y.  Both transactions are live since they both write their variables for the last time.  Notice that neither transaction reads any variable.  But the two possible candidates for H’ are: <R1, W1, R2, W2> (where R2 reads the y written by W1) and <R2, W2, R1, W1> (where R1 reads the x written by W2), so neither H’ candidate has the same set of transactions reading variables from each other.

Reduction: Is from Non-Circular Satisfiability.  Given a formula, they generate a “polygraph” of a database history.  A polygraph (N,A,B) is a directed graph (N,A) along with a set B of “bipaths” (paths that are 2 edges long).  If a bipath{(v,u), (u,w)} is in B, then the edge (w,v) is in A.  So, if a bipath exists in B from v to w, then an edge in A exists from w back to v.  This means that we can view a polygraph (N,A,B) as a family of directed graphs.  Each directed graph in the family has the same vertices and an edge set A’ that is a superset of A and contains at least one edge in each bipath in B. They define an acyclic polygraph as a polygraph (represented as a family of directed graphs) where at least one directed graph in the family is acyclic.

In the paper, they relate database histories to polygraphs by letting the vertex set N bet a set of live transactions.  We build edges in A (u,v) from transactions that write a variable (vertex u)  to transactions that read the same variable (vertex v).  If some other vertex w also has that variable in their read set then the bipath {(v,w), (w,u)} exists in B.  So edges (u,v) in A mean that u “happens before” v since u writes a variable that v reads.  A bipath {(v,w), (w,u)} means that w also reads the same variable, so must happen before u or after v.  They show that a history is serializable if and only if the polygraph for the history is acyclic.

So, given a formula, they build a polygraph that is acyclic if and only if the formula is satisfiable.  The polygraph will have 3 vertices (aj, bj, and cj) for each variable xj in the formula.  Each a vertex connects by an edge in A to its corresponding B vertex.  We also have a bipath in B from the b vertex through the corresponding c vertex back to the a vertex.

Each literal Cik  (literal #k of clause i) generates two vertices yik and zik.  We add edges in A from each yik to zi(k+1)mod 3  (in other words, the y vertex of each clause connects to the “next” z vertex, wrapping around if necessary).  If literal Cik is a positive occurrence of variable Xj, we add edges (cj, yik) and (bj, zik) to A, and the bipath {(zik, yik), (yik, bj)} to B.  If the literal is negative, we instead add (zik, cj) to A and {(aj, zik), (zik, yik)} to B.

If the polygraph is acyclic (and thus the history it represents is serializable), then there is some acyclic digraph in the family of directed graphs related to the polygraph.  So the bipath {(bj, cj), (cj, aj)} will have either the first edge from b-c (which we will represent as “false”) or will have the second edge from c-a (which we will represent as “true”).  (The directed graph can’t have both because its edges are a superset of A, which means it has the edge (aj, bj) and taking both halves of he bipath will cause a cycle).

If our acyclic directed graph has the “false” (b-c) version of the edge for a literal, then it also has to have the z-y edge of the bipath associated with the literal (otherwise there is a cycle).  If all of the literals in a clause were set to false, this would cause a cycle between these bipath edges and the y-z edges we added in A for each clause.  So at least one literal per clause must be true, which gives us a way to satisfy the formula.

If the formula is satisfiable, then build the acyclic digraph that starts with all of A, and takes the bipath edges corresponding to the truth value of each variable, as defined above.  This implies ways you need to take the edges from the bipaths for the literals, to avoid cycles.  The only way now for the graph to be acyclic is for there to be a cycle of x’s and y’s in the edges and bipath edges.  But that would imply that we’ve set all of the literals in a clause to false. Since we know that the clause can be made true (since the original formula is satisfiable), we know that a way exists to make the directed graph acyclic.

Difficulty: 7.  It takes a lot of baggage to get to the actual reduction here, but once you do, I think it’s pretty easy and cool to see how the cycles arise from the definitions of the graphs and from the formula.

Protected: Tableau Equivalence

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

Protected: Expected Retrieval Cost

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

Protected: Dynamic Storage Allocation

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