Skip to main content
MathOverflow

Return to Answer

added 1 character in body
Source Link
Per Alexandersson
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

This feels awfully related to the Subset-sum problem

If $m=(1,1,\dots,1)$$m=2(1,1,\dots,1)$, all the dot products will be the sum of subsets of components of $v$. If two such scalar product coincide, then you have solved an instance of subset-sum problem. So, your problem is at least NP-complete, in the number of dimensions.

This feels awfully related to the Subset-sum problem

If $m=(1,1,\dots,1)$, all the dot products will be the sum of subsets of components of $v$. If two such scalar product coincide, then you have solved an instance of subset-sum problem. So, your problem is at least NP-complete, in the number of dimensions.

This feels awfully related to the Subset-sum problem

If $m=2(1,1,\dots,1)$, all the dot products will be the sum of subsets of components of $v$. If two such scalar product coincide, then you have solved an instance of subset-sum problem. So, your problem is at least NP-complete, in the number of dimensions.

Source Link
Per Alexandersson
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

This feels awfully related to the Subset-sum problem

If $m=(1,1,\dots,1)$, all the dot products will be the sum of subsets of components of $v$. If two such scalar product coincide, then you have solved an instance of subset-sum problem. So, your problem is at least NP-complete, in the number of dimensions.