Re: np-complete

Restrict k=2. You can reduce SET PARTITION to this
problem.

Thanks.

--- Pinaki

--------------------------------------------------------------------------------------------------------


CubanBoy wrote:
the problem in fact return yes or no, and appear as a np complete
problem, but i need a demostration using another np complete problem.
transforming the input in another input in polinomical time, and later,
transform the output of the known problem in the input of mi problem.
is a metodological exercise.
one more time sorry for my bad english, i don´t found any other group
abaut the theme in spanish.

Sea A, a “size” t(a) e Z+ foreach aA and two values Z+, K y J,
said if elements in A se can be divided in K subsets A1,A2,…,AK
that
sum from i =0 to K of (sum foreach a in A of (t(a))^2 )<= J


Proginoskes ha escrito:

CubanBoy wrote:
Hay, im cuban, im trying to demostrate that the minimun sum of squares
is an np-complete problem, sorry for my bad english, if you have any
suggest or any clue, please conctact me at
nelly"at"infomed.sld.cu
change in the email adress "at" by @

You need to state precisely what your problem is.

First of all, minimization and maximization problems are not
NP-complete; NP-complete problems either return YES or NO.

You might be talking about the "threshold" version of a minimization
problem, such as:

INPUT: A sequence of numbers a(1), a(2), ..., a(n), and an integer k.
OUTPUT: Is there a nonzero subset S such that the sum of (a(i))^2, for
all i in S, is less than k?

--- Christopher Heckman

.