Permanent Evaluation

Going back to the problem we skipped over last week.

The problem: Permanent Evaluation.  This is problem AN13 in the appendix.

The description: Given an nxn matrix M of 0’s and 1’s, and a positive integer K, is the permanent of M equal to K?

Example: The permanent of M = \displaystyle \sum_\sigma \prod_{i=1}^n A_{i,\sigma(i)}

That is, for each permutation of the columns, we multiply down the main diagonal.  The sum of all of those products is the permanent.

1 2 3
4 5 6
7 8 9

..then the permanent is 1*5*9 + 1*6*8 + 2*4*9 + 2*6*7 + 3*5*7 + 3*4*8 = 450

Of course, we’re looking at 0/1 matrices, so I think what we’re really asking is how many permutations of the columns have 1’s on the main diagonal.

Reduction: If I’m right above that all we’re doing is counting how many ways there are 1’s in the main diagonal, then this becomes a pretty easy Turing Reduction from Hamiltonian Path.  Given an adjacency matrix of a graph, we want to know if the permanent of the adjacency matrix is 1 or more.  (Any Hamiltonian Path will give a permutation that multiplies to 1, and any permutation of vertices that is not a Hamiltonian Path multiplies to 0).   Given how complicated the “actual” reduction is, I’m a little worried that I missed something, though.

The reduction by Valiant that G&J point you to uses 3SAT, He shows that if you have a formula F, and define t(F) to be 2x the number of literals in F – the number of clauses in F, then there is some function f,  computable by a deterministic Turing Machine  in polynomial time, that maps a formula to a matrix.  (The matrix has entries in {-1..3}, he does another transformation later to convert it to a 0/1 matrix).  The permanent of that matrix = 4^{t(F)} * s(F) , where s(F) is the number of ways to satisfy F.

Since one of the consequences of Cook’s Theorem is that we can take an arbitrary non-deterministic Turing Machine and turn it into a Satisfiability formula, we get the reduction.

The actual construction of that function f is complicated.  Given a formula, we construct a graph and use the matrix as the adjacency matrix of the graph.  The variables, literals, and clauses get mapped to subgraphs.

Difficulty: If my way is right, I’d give it a 4- I think it’s easier than most Turing Reductions.  The Valiant construction is an 8.

Cosine Product Integration

I’m back from break, and we’ll go a little out of order at first since this is the last problem that’s similar to the ones we’ve been working on.

The problem: Cosine Product Integration.  This is problem AN14 in the appendix.

The description: Given a sequence of n integers (a_i..a_n), does \displaystyle \int_0^{2\Pi} (\prod_{i=1}^n cos(a_i\theta)) d\theta = 0?


Suppose our sequence was (1,2,3).  Then our integral is:

\displaystyle \int_o^{2\Pi}(\theta*2\theta*3\theta)d\theta

This is just 6\theta^3, which integrates to \frac{6x^4}{4}, which over the interval 0..2\pi is 24\pi^4

Reduction: This one is in Plaisted’s 1976 paper. In it, he notes that if you look at the function \displaystyle \prod_{j=1}^{k} (x^{a_j}+x^{-a_j}) the constant term in the power series expansion of that product is 0 if and only if the cosine integral is 0.  I have trouble seeing that myself.  The cooler thing is that you can make that constant term 0 if and only if you can take the sequence of a_i elements and partition them into 2 sets with the same sum.  So we can take an instance of the Partition problem, use the elements of the set as the elements of our sequence and then feed them into the product formulas.

Difficulty: It really depends on how easily you can see the connection between the cosine integral and the product formula (and, of course, how easily you could have thought of it). I find it hard, so I’m giving it an 8.

Periodic Solution Recurrence Relation

Probably the last post of the year- enjoy the holidays, everyone!

The problem: Periodic Solution Recurrence Relation.  This is problem AN12 in the appendix.

The description: Given a set of m ordered pairs (c_1,b_1) through (c_m, b_m with each b_i >0, can we find a sequence a_0 though a_{n-1} of integers, such that if we build the infinite sequence \displaystyle a_i = \sum^m_{j-1} c_j*a_{i-b_j} is periodic: that is, a_i \equiv a_{i (mod \: n)} for all i?

Example: Here’s a super simple example: m=2 and the pairs are (1,1) and (2,2).  This gives us the recurrence a_i = a_{i-1}  + 2a_{i-2}.  If we start with 1,1, this gives the sequence 1,1,3,5,11,21,43,…  which is periodic mod 10 (the last digit always repeats 1,1,3,5)

Reduction: This shows up in Plaisted’s 1984 paper.  He mentions it as a corollary to his Theorem 5.1 which showed that Non-Trivial Greatest Common Divisor and Root of Modulus 1 were NP-Complete.  Similar to the Root of Modulus 1 problem, we build a polynomial from a set of clauses that has 0’s on the unit circle.  The polynomial also has a leading coefficient of 1.  This means, apparently, that the recurrence relation corresponding to the polynomial has a periodic solution if and only if the polynomial has a root on the complex unit circle, which only happens if the original 3SAT formula was satisfiable.

Difficulty: 8.

Number of Roots for a Product Polynomial

The problem: Number of Roots for a Product Polynomial.  This is problem AN11 in the appendix.

The description: Given a set of sequences A1 through Am , each Ai containing a sequence of k pairs (a_i[1],b_i[1]) through (a_i[k],b_i[k]) , and an integer K.  If we build a polynomial for each Ai by \displaystyle \sum_{j=1}^k a_i[j]*z^{b_i[j]}, and then multiply all of those polynomials together, does the resulting product polynomial have less than K complex roots?

Example:  Suppose A1 was <(1,2), (2,1), (1,0)>, A2 was <(3,3), (2,2), (1,1), (0,0)>, and A3 was <(5,1), (7,0)>.  These represent the polynomials x2+2x+1, 3x3 + 2x2 + x, and 5x+7.  (I’m pretty sure it’s ok for the sequences to be of different length, because we could always add (0,0) pairs to shorter sequences).  This multiplies out to 15 x6 + 61 x5 + 96 x4+ 81 x3 +  50 x2 + 26x +7, which has 4 distint complex roots, according to Mathematica.

Reduction: This is another one that uses Plaisted’s 1977 paper.  (It’s problem P4).  He builds the polynomials PC and QC in the same way that he did in the reduction for Non-Divisibility of a Product Polynomial.  One of the statements that he says is “easy to verify” is that The product of the Q polynomials for each clause has N (for us, K) zeroes in the complex plane if and only if the original 3SAT formula was inconsistent.

Difficulty: I’m giving all of these problems based on the polynomials that come from a formula an 8.

Root of Modulus 1

After taking a week off for Thanksgiving, we move on to another equation problem.

The problem: Root of Modulus 1.  This is problem AN10 in the appendix.

The description: Given a set of ordered pairs (a_1,b_1) through (a_n, b_n) of integers, each b_i is non-negative.  Can we find a complex number q where \mid q \mid= 1 such that \displaystyle \sum_{i=1}^n a_i * q^{b_i} =0?

Example: It was hard for me to come up with an interesting example (where q is not just 1 or i), so thanks to this StackOverflow post for giving me something I could use.

Let our ordered pairs be (5,2), (-6,1), and (5,0).  This gives us the polynomial 5x2-6x+5.  Plugging these into the quadratic formula get us the roots \frac{3}{5} \pm  \frac{4}{5} i, which is on the complex unit circle.

Reduction: This one is again from Plaisted’s 1984 paper.  It again uses his polynomial that we’ve seen in some other problems (most recently Non-Divisibility of a Product Polynomial).  So again, we start with a 3SAT instance and build the polynomial.  He starts by showing that if you have a polynomial with real coefficients p(z), then p(z)*p(1/z) is a real, non-negative polynomial on the complex unit circle, and it has zeros on the unit circle exactly where p(z) does.

Then, we can do this for the sum of the polynomials made out of each clause, which means that this new polynomial has 0’s on the unit circle exactly where the original one did.  Which means it has a 0 on the complex unit circle if and only if the formula was consistent.

Difficulty: 8.  I’m starting to appreciate the coolness of turning a formula into a polynomial, and how it makes a lot of problems easier.  I just wish it was clearer to see how it all works.


Algebraic Equations over GF[2]

AN8 is Quadratic Diophantine Equations.

The problem: Algebraic Equations over GF[2].  This is problem AN9 in the appendix.

The description: Given a set P of m polynomials over n variables (x1 through xn) where each polynomial is the sum of terms that is either 1 or the product of distinct xi, can we find a value ui for each xi in the range {0,1} that make each polynomial 0, if we define 1+1=0, and 1*1 = 1?

Example: It helps to think of GF[2] as a boolean logic world, where + is XOR and * is AND.  So, suppose we have three variables, and the polynomials:

  • P1 = 1 + x1x2 + x2x3
  • P2 = x1 + x1x2x3

..Then setting x1=0, x2=1, x3=1 makes both polynomials 0.

Reduction: G&J say that Fraenkel and Yesha use X3C, but the paper I found uses 3SAT.  We’re given an equation that has n variables and m clauses.  The variables of our polynomials will be the same variables in the 3SAT instance.  For each clause, we build a polynomial by:

  • Replacing a negated literal (~x) with the equation 1 + x.  (Remember, + means XOR in this system)
  • Replacing an OR clause (A ∨ B) with the equation A+ B +A*B
  • Xoring the whole above thing with 1.

Notice that the first replacement makes ~x have the opposite truth value of x, the second replacement rule is logically equivalent to A∨B, and the third part makes the polynomial 0 if and only if the clause evaluated to 1.  So the polynomial is 0 if and only if the clause is satisfiable.  So all polynomials are 0 if and only if the all clauses are satisfiable.

Difficulty: 5.  This is easy to follow.  It’s a little tricky to make students come up with the equivalence rules above, but I think if you can explain it right, it’s not that bad.

Non-Divisibility of a Product Polynomial

Now back to the problem we skipped over last week.

The problem: Non-Divisibility of a Product Polynomial.  This is problem AN6 in the appendix.

The description: Just like Non-Trivial Greatest Common Divisor, we’re given a set of m sequences of pairs of  integers (so sequence Ai is <(ai[1],bi[1]) …(ai[k],bi[k])>), where each b element is ≥ 0.  We’re also given an integer N.

Just like Non-Trivial Greatest Common Divisor, we build the polynomials \displaystyle \sum_{j=1}^k a_i[j]*z^{b_i[j]}, for each i from 1 to m.  But now we want to multiply them all together.  If we do, is the product not divisible by zN-1?

Example: Suppose A1 was <(1,3), (2,2), (-1,1), (-2,0)> and A2 was <(5,4), (3,2), (7,0)>.  Then A1‘s polynomial is z3 + 2z2-z-2, and A2‘s polynomial is 5z4+3z2+7.  The product of these is: 5z7+10z6 -2z5 – 4z4 + 4z3 + 8z2-7z-14.  If N=2, then it turns out that z2-1 is a factor (it’s actualy a factor of A1), so the decision problem would say “No”.

Reduction: The reduction for this is again by Plaisted, using his polynomials that come from logical statements. For each clause C of a 3SAT formula, you build the polynomial PC for that clause, and from that QC = (xN-1)/PC  He mentions in his paper that it is “easy to verify” (but doesn’t actually prove it) that The product of all of these QC‘s / (xN-1) is analytic iff S is inconsistent.  I think the reason is that QC represents in his polynomial the ways to assign variables to make a formula false. So if all assignments make it false, the product is equal to all assignments.  I still don’t quite see how the divisibility follows.

Difficulty: 8.  It’s about as hard as the last one.

Non-Trivial Greatest Common Divisor

We’ll do this next one out of order because I think this order is better explained by the paper.

The problem: Non-Trivial Greatest Common Divisor.  This is problem AN7 in the appendix.

The description: Given a set of m sequences of pairs of  integers (so sequence Ai is <(ai[1],bi[1]) …(ai[k],bi[k])>), where each b element is ≥ 0.  I’m pretty sure k can be different in each sequence.  If we build the polynomials \displaystyle \sum_{j=1}^k a_i[j]*z^{b_i[j]}, for each i from 1 to m, does the greatest common divisor of those polynomials have degree greater than 0?

Example: I think the hardest part of this description is picturing the polynomials, so here’s a simple example showing how that works.  Suppose m=2, and A1 was <(20,3),(4,2),(30,1)> and A2 was <(2,4),(8,1)>

(As an aside, I wish G&J didn’t use A for both the name of a sequence and lowercase a for the name of one of the entries of each pair.  They’re not related.)

The polynomial corresponding to A1 is 20x3 + 4x2+30x, and the polynomial corresponding to A2 is 2x4 +8x.  The polynomial 2x is a divisor of both, and I think it’s the GCD.  (If not, the GCD is larger, and so also has degree >0).  So, this problem instance would have the answer “yes”.


This reduction is also by Plaisted, who did last week’s reduction, but is in his 1984 paper.  His reduction is from 3SAT.  In the paper, he gives an algorithm that turns a logical formula into a polynomial.  The polynomial p that gets created has the property that p(z) = 0 if and only if z is an M-th root of unity (a solution to zM=1).  This leads to a way of setting the truth values of the logical formula: if ω is the root of unity, set variable Pj to true if ω^{M/q_j}=1, where qj is the jth prime number.  It turns out if you do that, you make the entire logical formula true.

So, for our problem, we’re handed a 3SAT instance with n variables.  Let M be the product of the first n primes.  The formula is satisfiable iff we can make all clauses true, which happens iff there is an Mth root of unity ω such that the polynomial on each clause is 0 (so we make a polynomial for each clause in the SAT formula). He states an “easy” identity (without proof) that the polynomial of A∧B is the gcd of the polynomials of A and B.  So therefore if ω exists for all polynomials, the gcd has degree greater than 0.

Difficulty: 8.  This is a little easier to follow because he states the properties of his polynomial up front.  I’d like to see more proofs of his “easy” properties and to be honest, I’m not sure how the last step happens (how having ω exist means that the gcd has degree > 0).  I also don’t know how you’d ask students to come up with these polynomials on their own.

Exponential Expression Divisibility

AN4 is Comparative Divisibility.

This next problem is related to one we’ve done before, but I think it merits its own entry.

The problem: Exponential Expression Divisibility.  This is problem AN5 in the appendix.

The description: Given two sequences A = and B=b1..bof positive integers, and an integer q. Does \displaystyle \prod_{i=1}^{n} (q^{a_{i}}-1) divide \displaystyle \prod_{i=1}^{m} (q^{b_{i}}-1)?

Let A={2,3} and B={1,4,5}.  If q=4, then the first product comes to 15×63=945 and the second product comes to 3x255x1023 = 782,595.  These two numbers don’t divide.

Reduction: Plaisted’s paper calls this a “refinement” of Polynomial Non-Divisibility.

The reduction for that built a polynomial called “Poly(Cj)”  and showed xN-1 is a factor of \displaystyle \prod_{j=1}^kPoly(~Cj)(x) if and only if S is inconsistent.  As I said in that post, there was a lot I don’t understand about it, because he doesn’t give clear proofs or explanations.  He uses some more manipulations to say that the SAT formula is inconsistent iff 2mn-1 divides \displaystyle \prod_{j=1}^{k} \frac{(2^{mn}-1) * Denom(C_j)(2^m)}{Num (C_j)(2*m)} .  (“Num” and “Den” were used in the creation of “Poly”).  This gives us a restatement of the Exponential Expression Divisibility problem where q =2.  Since there was nothing special about the 2, it could work for any integer and thus the reduction works in general.

Difficulty: 9.  Just like the Polynomial Non-Divisibility problem, I have a very hard time following what he’s doing here.  I wish I could find some better explanations

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.