C A L LF O RP A P E R S
===
The 2009 International Conference on Frontiers in
Education: Computer Science and Computer Engineering
FECS'09
Date and Location: July 13-16, 2009, La
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 \ne
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 wrote:
> Can't you just sort the numbers, and than multiply first k numbers, than
> second etc. ?
>
> 2009/3/8 Ji
Can't you just sort the numbers, and than multiply first k numbers, than
second etc. ?
2009/3/8 Jim
>
> 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
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
