An Old Strange Observation

Assume FACTOR and SUBSET-SUM are independent of the digital base you choose for their constituents. Then why would they have different complexity? Its a, meaningless, observation that FACTOR just looks harder than SUBSET-SUM in it's digital circuit form.

Let subsum({5,3,4}) = 7 be the question if summation of a subset equals 7. Now, that is equal to the question, is there a vector v such that (5,4,3).v = 7? We could encode that digitally such that <5><4><3>∗<v> = <x><7><y>, where constants are zero padded and rest are unknowns. Now, a blackboard multiplication:

            <5><3><4> . vi
         <5><3><4>    . vj 
      <5><3><4>       . vk
    ----------------------+
      < x  ><7>< y  >

Where the bits vi..vk are part of v. There seems to be some structural relation between FACTOR and SUBSET-SUM, if you could divide unknowns NP would be easy.

So, more precise, FACTOR equals <x>∗<y> = <c>, where c a constant, and SUBSET-SUM -apart from its trivial encoding- also reduces to <c>∗<v> = <x><d><y>, where c and d constants, v intermixed with zeroes. Great, now what? It feels like the same problem.

Hogwash.


Silliness... How did XOR-SAT work again? Right, carry cannot be expressed in XOR form.