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 of rationals such that at least K of the m-tuples, when multiplied by , are at least 0?

**Example: **Suppose our tuples were:

- {1,1,1}
- {-1,-1,-1}
- {1,-1,1}
- {-1,1,-1}

If K = 2, we can choose 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 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 = and d = m+1+3t. We will create d-tuples as follows.

- “A” vectors: 2
^{3t}copies of “positive” and “negative” vectors for each variable. So variable i has vectors A_{i}= 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. ~A_{i}is similar, except the first 1 is replaced by a -1. - 2
^{t}“B” vectors for each variable (positive and negative). So variable i has vectors B_{i}= 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. ~B_{i}is similar, but the 4 is replaced by -4. - One “C” vector for each clause. If the clause had variables x
_{i}and x_{j}, the clause would be: i-1 0’s followed by 4*the sign of x_{i}, followed by j-1 0’s, followed by 4* the sign of x_{j}followed by m-j 0’s followed by 1 followed by 3t 0’s.

By “the sign of x_{i}“, I mean 1 if x_{i} 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+2^{3t}+m*2^{t}+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 :

- 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*2
^{3t}-2^{2t}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 2
^{t}B_{i}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 2^{t}B_{i}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.

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