And while I’m at it

Yaroslav Bulatov sent me the following nice question. Given vectors (a1,…,an) and (b1,…,bn) in Rn, is there an efficient algorithm to decide whether sgn(a1x1+…+anxn) equals sgn(b1x1+…+bnxn) for all x in {0,1}n? I could think about it myself, but wouldn’t it be more fun to call upon the collective expertise of my readers? After all, this is a Serious Blog now. I await the observation that’s eluded me for the past five minutes.

9 Responses to “And while I’m at it”

  1. Anonymous Says:

    Doesn’t this mean that the vectors are
    linearly dependent, related by a positive

    Assume that a’,b’ have this property.
    Normalize these to unit vectors a,b which
    will still clearly have the property.

    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.


  2. Kurt Says:

    Scott, how are those vectors being specified? Are they actually in Q^n and not R^n? I ask that because, if you think like Andrej Bauer, sgn(x) for x ∈ R is not even computable.

  3. Kurt Says:

    This post has been removed by the author.

  4. Anonymous Says:


    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.

  5. Anonymous Says:

    oh, I didn’t see the {0,1}^n. oops, ok, more interesting now.


  6. David Says:

    Yes there is. Check every pair (sgn(Ai), sgn(Bi) ) and if any are different, you can construct X s.t. it is 1 for Xi and 0 for all others.

    I’ll prove this is exhaustive later.

  7. Anonymous Says:

    David: a=(3,-2), b=(1,-2), x=(1,1)?

    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?)

  8. Yaroslav Says:

    Thanks Anonymous, I think your argument works

  9. Scott Says:

    Thanks, anonymous. I figured there was probably a reduction from Subset Sum, but I suck at reductions.