I don't have polynomial algorithm for this problem, after asking for help from many persons who are skilled at algorithm design. So I suspect this problem is another NP-complete problem.
Your hint is great that this problem is possibly neither NP-complete nor P. You says, "The only problem i know which contains multiplication is computing a "permanent",...", what's the problem, any details or links? thank you. 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 -~----------~----~----~----~------~----~------~--~---
