Open Hemisphere

I’m going to be out of town for the next 2 weeks, so we’ll be going on a bit of a hiatus.

The problem: Open Hemisphere.  This is problem MP6 in the appendix.

The description: Given a set X of m-tuples of integers, and a positive number K, can we find an m-tuple  \bar{y} of rationals such that at least K of the m-tuples, when multiplied by \bar{y}, are at least 0?

Example: Suppose our tuples were:

  1. {1,1,1}
  2. {-1,-1,-1}
  3. {1,-1,1}
  4. {-1,1,-1}

If K = 2, we can choose \bar{y} to be {1,0,1}.  This multiplied by tuples 1 and 3 would be positive (with a value of 2).  We could have also chosen {-1,0,-1} to make the multiplication with tuples 2 and 4 positive.  I don’t think there is a legal \bar{y} if K=3.  There certainly isn’t if K=4 (you can’t make both tuple 1 and tuple 2 positive simultaneously).

Reduction: Johnson and Preparata use Max-2-Sat.   So we’re given a 2-Sat instance with s clauses, m variables, and a target N, the number of clauses we need to satisfy.  Let t = \lceil log_{2}(ms+1) \rceil and d = m+1+3t.  We will create d-tuples as follows.

  • “A” vectors: 23t copies of “positive” and “negative” vectors for each variable.  So variable i has vectors Ai = i-1 0’s, followed by 1 followed by m-i 0’s, followed by 1, followed by each permutation of 1 or -1 of length 3t.  ~Ai is similar, except the first 1 is replaced by a -1.
  • 2t “B” vectors for each variable (positive and negative).  So variable i has vectors Bi = i-1 0’s, followed by 4, followed by m-i 0’s followed y -2, followed by 2t 0’s, followed by each permutation of 1 or -1 of length t.  ~Bi is similar, but the 4 is replaced by -4.
  • One “C” vector for each clause.  If the clause had variables xi and xj, the clause would be: i-1 0’s followed by 4*the sign of xi, followed by j-1 0’s, followed by 4* the sign of xj followed by m-j 0’s followed by 1 followed by 3t 0’s.

By “the sign of xi“, I mean 1 if xi shows up as a positive literal, and -1 if it shows up as a negated literal.  It’s also worth noting that since t is based on the log of the input size, creating a number of vectors that is exponential in t still keeps the input size of our hemisphere instance polynomial.

Our K will be 2m+23t+m*2t+N.  (All of the A tuples, half of the B tuples, and N of the C tuples)

If we have a Max-2-Sat solution, here’s how you build the \bar{y}:

  • Positions 1-m correspond to variables.  If the variable is set positively, put a 1 in that position.  If the variable is set negatively, put a -1 in that position.
  • Put a 1.5 in position m+1
  • Put a 0 everywhere else.

This will multiply positively with all A tuples, half of the B tuples, and  N of the C tuples.

If we have a hemisphere solution, it has to fit certain criteria:

  • At least 2m*23t-22t of the A vectors multiply positivly with our solution (this is how many you need even if all B and C vectors multiply positively)
  • Position m+1 of the solution vector is > 0 (otherwise not enough A vectors are positive)
  • At most 2t Bi vectors multiply positively with our solution for each variable i.  (Position m+1 of the B vector is the -2.  If we have more than 2t Bi vectors we’ll set position m+1 in the solution vector negative)
  • Position m+1 of the solution vector is  at least as big as the sum of the absolute values of the values in positions m+2+2t through m+1 + 3 (If it wasn’t, the limit on the B vectors would mean we wouldn’t be able to take enough A vectors to get a hemisphere solution)
  • Each value in the first m positions in the solution vector is at least as big as the absolute value of (position m+1) /4  (You can prove this by contradiction using algebra).  Importantly, this means those values can’t can’t be 0.
  • We must have at least N C tuples that multiply positively with the solution vector (given the limits on A and B).

Using these facts, we can find the ways to set the variables: Each of the first m positions in the solution vector correspond to a variable.  If the value at that position is positive, set it to true, if the value is negative, set it to false.  This will satisfy the N clauses that correspond to the C tuples that were made positive in the hemisphere solution.

Difficulty: 9.  Notice how much work has to happen to get around the fact that the hemisphere could have rational answers.  Also, notice how many tuples you need to get this reduction.  I’m also not 100% convinced yet that there isn’t a hole in the various claims about how the hemisphere solution has to behave that allows some weird combination of values to fall through.

One response to “Open Hemisphere

  1. Pingback: Modular square roots of -1 – Poly-time Reduction

Leave a Reply

Your email address will not be published. Required fields are marked *