There’s a reduction from subset sum. Let S=(s1, …, sn) be an instance of subset sum (integer entries, we’re looking for a subset that sums to 0). Define a and b so that:

ai = si + 1/3n

bi = si – 1/3n

for every i. Then the absolute difference between a sum from a and a sum from b is always less than one, and the signs of the sums differ if and only if the corresponding sum of entries from S sums to 0. So the problem is NP-complete.

(Any errors in this?)

]]>I’ll prove this is exhaustive later.

]]>–Troy

]]>Why does sgn(a dot (a-b)) have to equal

sgn(b dot (a-b))? The equality was only

specified for vectors in {0,1}^n

which a-b might not be.

linearly dependent, related by a positive

coefficient?

Assume that a’,b’ have this property.

Normalize these to unit vectors a,b which

will still clearly have the property.

Now

sgn(a dot (a-b))=sgn(b dot (a-b)).

Notice that if sgn(x)=sgn(y) then also

sgn(x+y)=sgn(x)=sgn(y). Applying this to

the above with x=a dot a – a dot b

and y=b dot a – b dot b we have

sgn(a dot a – a dot b)=0 and so

a dot b=1 and a=b. Thus the two

original vectors are linearly independent,

related by a positive coefficient.

–Troy

]]>