Author |
Topic: Distinct Dot Products (Read 1270 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Distinct Dot Products
« on: Sep 29th, 2004, 3:32pm » |
 Quote  Modify
|
This is a problem I accidentally made up. Not sure how to solve it ... maybe it is interesting.
Given a fixed nx1 vector of naturals V, how many distinct dot products S.V exist, where S is an nx1 vector over {-1,+1}?
In other words, if I have to add up a bunch of numbers, how many distinct sums can I make if I'm allowed to twiddle with their signs? My first response was orbit-stabilizer theorem, but I can't figure out the group action.
|
| « Last Edit: Sep 29th, 2004, 3:32pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Distinct Dot Products
« Reply #1 on: Sep 29th, 2004, 4:54pm » |
Quote Modify
|
I think it is NP-complete to even determine if the number of distinct sums is 2n or not. It seems to be equivalent to the subset sum = 0 problem considering the set to be the of 2n numbers with + and - signs.
I doubt if there will be a 'simple' closed form solution to this.
There sure could be closed forms solutions. But those most likely could not be evaluated in polynomial time.
Just thought it might be relevant. Sorry if it is not.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Distinct Dot Products
« Reply #2 on: Sep 30th, 2004, 10:51am » |
Quote Modify
|
Sorry, the 2n numbers have a trivial subset which sums to zero. Maybe there is an different form of the subset sum problem which applies here.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Distinct Dot Products
« Reply #3 on: Oct 10th, 2004, 1:31am » |
Quote Modify
|
on Sep 29th, 2004, 4:54pm, Aryabhatta wrote:| I think it is NP-complete to even determine if the number of distinct sums is 2n or not. It seems to be equivalent to the subset sum = 0 problem considering the set to be the of 2n numbers with + and - signs. |
|
IMHO, even the problem of determining if a particular sum s may be achieved as a described dot-product is NP-complete, since it’s equaivalent to a Knapsack Problem with sum = (N+s)/2, where N is the sum of all numbers in V.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Distinct Dot Products
« Reply #4 on: Oct 24th, 2004, 10:36am » |
Quote Modify
|
Interesting, although my problem may be easier than determining if a particular sum is possible, since I dont require any specific information aside from the number of possibilities.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Distinct Dot Products
« Reply #5 on: Oct 25th, 2004, 2:53pm » |
Quote Modify
|
on Oct 24th, 2004, 10:36am, william wu wrote:| Interesting, although my problem may be easier than determining if a particular sum is possible, since I dont require any specific information aside from the number of possibilities. |
|
It is NP-complete even to decide if the number of distinct sums is Odd or Even.
Here is a proof.
Fact 1) PARTITION is NP-Complete.
PARTITION: Given integers c1, ..., cn, does there exist an S [subseteq] {1,2,...,n} such that [sum]j[in]Scj = [sum]j[notin]Scj.
We can easily show the PARTITION remains NP-complete even if ci's are all assumed to be positive.
Fact 2) Give an nx1 vector V of natural numbers, the number of distinct dot products S.V where S is an arbitrary vector over {-1,+1} is odd if an only if there is some S' (over {-1,+1}) such that V.S' = 0.
Proof of Fact 2) Let {A1, ..., Ak} be the set of distinct dot products. Clearly -A1,...,-Ak are also part of the same set. So we can pair off the non-zero dot products, with their negatives. Thus k is odd if and only if 0 is in the set. []
Now V has a partition if and only if there is some S' such that V.S' = 0.
Thus V has a partition if and only if the number of distinct dot products is odd and hence determining the parity of the number of distinct dot products is NP-Complete.
|
| « Last Edit: Oct 25th, 2004, 2:55pm by Aryabhatta » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Distinct Dot Products
« Reply #6 on: Oct 25th, 2004, 11:58pm » |
Quote Modify
|
Bravo Aryabhatta! In playing with the problem, I had also observed that {-A1,...,-Ak} are part of the same set, but you found a way to really capitalize on this fact. Thanks.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print