Having read the "permanent" on wikipedia site, I think there is little correlation with this problem.
Thanks for your clarification, and i realize the special case of my problem can reduce to this partition problem: Given a set of 2*k positive numbers(where n is 2), how to split this set into two halves, each half holds k numbers, and minimize the difference of two halves' sum? It's known to be a classic NP-Complete, right? Miroslav Balaz wrote: > so there is no problem, it works if you take logarithm you have the > partition 18:18, which is optimal as the sum us 36 > > the permanent: > the determinant is calculated by taking all permutations , and for each > permutation you multiply some elements of matrix, given by that permutation. > and then you sum it up, BUT you are also give sign according parity of > permutation. > > In computing the permanent there is no such sign. you should look to book > Complexity theory:A modern approach, by arora and (sorry i dont remeber > second author name exactly) > > 2009/3/10 Jim <arkma...@gmail.com> > > > > > sorry, I fail to understand "the permanent" :-( > > > > If numbers are powers of 2, and the input are these exponent. > > but I think they are different problems. > > say, the original numbers are 2, 4, 8, 16, 32, 64, 128, 256, > > the minimal partition is [8, 16, 32, 64] [2, 4, 128, 256] > > sum is 524288. > > > > while the corresponding exponent inputs are > > 1, 2, 3, 4, 5, 6, 7, 8 > > and there are so many partition problems, which maximum partition > > produce the result, [1,2,7,8] [3,4,5,6]? > > > > thanks > > > > Miroslav Balaz wrote: > > > so the permanent is like determinant but without sign in summand. > > > > > > I have found something interesting in your peoblem. > > > > > > It is NP-complete if you have n=2, and numbers are powers of two, but on > > > input is only exponent. > > > som if there is number 2^100, only 100 is on input. One can directly > > reduce > > > MAX-PARTITION to this problem. This alone has no value, because it is > > > different problem, because the input if of log n size, as if it was in > > your > > > problem. > > > > > > 2009/3/9, Jim <arkma...@gmail.com>: > > > > > > > > > > > > After asking for helps from many persons who are skilled at algorithm > > > > design, I suspect this problem is a NP-complete. > > > > The only problem you speak of which contains multiplication is > > > > computing a "permanent", what is this problem? > > > > could you post any details or links about it? > > > > > > > > You are probably right that this problem is neither NP-complete nor P. > > > > Great hint. > > > > > > > > Thank you very much. > > > > > > > > > > > > On Mar 9, 12:07 am, Miroslav Balaz <gpsla...@googlemail.com> wrote: > > > > > Do you have polynomial algorithm for that problem? > > > > > We don't need one another NP-copmlete problem. There is enough of > > them. > > > > > > > > > > And there are more interresting problems for which we don't know > > > > reduction. > > > > > The rule of thumb is, that if you pick random problem from NP that it > > is > > > > not > > > > > from P. > > > > > Assuming P \neq NP, there may be problems in NP that are not > > NP-complete > > > > and > > > > > are not in P. > > > > > > > > > > This problem contains ARITHMETIC MULTIPLICATION. > > > > > The only problem i know which contains multiplication is computing a > > > > > "permanent", but that is PSPACE complete, i think, but i am not sure. > > > > > You should try to find proof of NP completeness of knapsack > > > > > problem(google). > > > > > > > > > > If you want to make any success, you should first try case when all > > > > numbers > > > > > are power of two. > > > > > > > > > > > > > > 2009/3/8 Jim <arkma...@gmail.com> > > > > > > > > > > > > > > > > > > > > > > > > > it's incorrect. for example: > > > > > > 23, 24, 26, 30, 32, 63, 64, 90, n = 2, k = 4 > > > > > > the minimum split is [26, 30, 32, 90] [23, 24, 63, 64] > > > > > > the sum is 4472064 > > > > > > > > > > > On Mar 8, 10:08 pm, Miroslav Balaz <gpsla...@googlemail.com> > > wrote: > > > > > > > Can't you just sort the numbers, and than multiply first k > > numbers, > > > > than > > > > > > > second etc. ? > > > > > > > > > > > > 2009/3/8 Jim <arkma...@gmail.com> > > > > > > > > > > > > > Given a set of k*n positive numbers, we can split this set into > > n > > > > > > > > partitions, each partition with k numbers. Now, we multiply the > > > > > > > > numbers in each partition, got n products, then we have a sum > > of n > > > > > > > > products. How can we split this set to minimize this total sum? > > > > > > > > > > > > > It's easy to show this problem is NP. Since we can recast this > > > > > > > > optimization problem as a decision problem, how can we split > > this > > > > set > > > > > > > > and let this sum is not greater than a given number t, which is > > no > > > > > > > > harder than original optimization one. Given an instance of > > this > > > > > > > > decisive problem, we can easily compute this sum within O(n) > > time. > > > > > > > > > > > > > The key part is which known NP-complete problem reduces to this > > > > > > > > problem. Unfortunately, I have no idea about this polynomial > > > > > > > > reduction. (find a minimum weighted maximal matching with a > > > > > > > > hypergraph?) > > > > > > > > > > > > > Any hints will be appreciated, thanks. > > > > > > > > > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
