«
»

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.

Email, RSS Follow

This entry was posted on Friday, April 21st, 2006 at 3:47 am and is filed under Complexity. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

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

  1. Anonymous Says:
    Comment #1 April 21st, 2006 at 9:53 am

    Doesn’t this mean that the vectors are
    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

  2. Kurt Says:
    Comment #2 April 21st, 2006 at 10:03 am

    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:
    Comment #3 April 21st, 2006 at 10:17 am

    This post has been removed by the author.

  4. Anonymous Says:
    Comment #4 April 21st, 2006 at 10:21 am

    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.

  5. Anonymous Says:
    Comment #5 April 21st, 2006 at 10:25 am

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

    –Troy

  6. David Says:
    Comment #6 April 21st, 2006 at 10:53 am

    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:
    Comment #7 April 21st, 2006 at 1:19 pm

    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:
    Comment #8 April 21st, 2006 at 3:33 pm

    Thanks Anonymous, I think your argument works

  9. Scott Says:
    Comment #9 April 21st, 2006 at 6:06 pm

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