Tag Archives: 3SAT

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 \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 \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 \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 \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”.

Reduction:

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.

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.

Quadratic Congruences

On to the next section!  The “Algebra and Number Theory” section should take us through the end of the year.

The problem: Quadratic Congruences.  This is problem AN1 in the appendix.

The description: Given positive integers a,b, and c, can we find a positive integer x < c such that x2 ≡ a (mod b)?

Example: Let a = 3, b = 7, c = 13. It turns out that for every x < c, x2≡ either 0,1,2 or 4 mod b.   So this isn’t solvable.  But if we change a to 2, then the first c that works is 3.

One thing I learned in doing this problem is that the squares of mod b will always form a cycle with period b.  The proof is a pretty cool algebra problem if you set it up right.

Reduction: The paper by Manders and Adleman uses 3SAT.  Starting from the list of variables, they define a set Σ that holds all 3-element clauses of 3 different literals from that list of variables.  We won’t actually build this set (that’s exponential), but we can list out a number j for each of those clauses.  Then define τΦ to be -1* the sum of 8j for each of the j numbers that correspond to the clauses in our actual formula.

For each variable i, we define fi+ to be the sum of 8j for each j number in ∑ that has that variable positively, and fi to be -1* the sum of 8j for each number in Σ that has the variable negatively.

Let m be|Σ|, and set n=2m +The number of variables, and define a set C wit values c0 through cn:

  • c0 = 1
  • If j is odd(=2k-1) and ≤ 2m, cj = -8k/2
  • If j is even (=2k) and ≤ 2m, cj = -8k
  • If j is > 2m (= 2m+i), then cj = (fi++fi)/2

Set τ = τΦ + The sum of all of the ci‘s + The sum of all of the fi‘s.

This actually turns into a Subset Sum problem: Let C be our set, and count each value positively if we take it, and negatively if we don’t take it.

But we still need to prove this is SOS problem is solvable exactly when the original problem is.

Create a set p0 .. pn of consecutive prime numbers where the first one (p0) is 13.  Then define a set of θj values as the smallest number satisfying:

  • θj≡ ci (mod 8m+1)
  • θj ≡ 0 (mod The product of each (pi)n+1, except for j.)
  • θj is NOT ≡ 0 (mod pj)

Set H = The sum of all of the θj‘s.  Set L=the product of all of the (pi)n+1.  We are finally ready to create our Quadric Congruence instance:

b = 2*8m+1*K.

Let d = The inverse of (2*8m+1+K), mod b.

Then a = d*(K*τ2+2*8m+1 * H2)

c = H.

From here, it’s a bunch of algebra to show that an x exists if and only if the original formula was satisfiable.

Difficulty: 9.  Maybe it should be 10.  I don’t know enough number theory to be convinced that the θ’s exist, and be computed in polynomial time.  The algebra I’m glossing over is pretty complicated as well.

Protected: Traveling Salesman Polytope Non-Adjacency

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

Protected: Integer Programming

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

Protected: Deadlock Avoidance

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