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 -~----------~----~----~----~------~----~------~--~---
