In primul rand, pentru cei care nu stiu problema:

Se dau n numere in intervalul deschis (0,1) si se cere
sa se determine care este numarul minim de
'urne'(bins) de marime unitara(1) care pot fi folosite
pentru a 'tine'(pack) toate cele n numere. O urna
poate tine orice sub-multime a celor n numere a caror
suma nu depaseste 1.

Problema este NP-Completa.

In primul rand ea este clar NP, deoarece daca se
specifica un certificat alcatuit din un numar k si
continutul fiecarei din cele k urne este usor
verificabil daca fiecare urna contine numere a caror
suma nu depaseste 1, si daca fiecare numar a fost
distribuit in fix o urna.

Demonstratia de NP-Completitudine se face prin
reducere de la problema sumei sub-multimii, care este:

Se dau n numere, b1, b2, .. bn, si un numar S. Se cere
sa se determine daca exista o sub-multime de numere
astfel incat suma lor sa fie fix S.

Vom demonstra ca daca problema urnelor poate fi
rezolvata in timp polinomial si problema sume
sub-multimii poate fi rezolvata in timp polinomial.

Fie o instanta oarecare (b1,b2,.., bn, S)=P1 a
problemei sumei sub-multimii. Fara a pierde
generalitate presupunem ca 0<bi<S. (Deoarece orice
numar care nu satisface aceasta restrictie nu poate
contribui la solutie).

Notam cu T = b1+b2+..+bn, suma celor n numere.
Se observa ca a gasi bk1 + bk2 + .. + bkj = S este
echivalent cu a gasi bl1 + bl2 + .. +bli = T-S.
(Deoarece daca s-a gasit bl1, bl2,... celelalte numere
dau suma T-(T-S) = S)
In continuare vom presupune ca S<=(T/2). (Contrar
reducem problema c.f. mai sus)

Obs. S<=T/2 => T-S>S.
Observam ca 0 < (bi/(T-S)) < 1.
Cum T-S>S => bi/(T-S) < bi/S si cum bi<S => bi/S < 1
=> bi/(T-S)<1.
Cum bi>0 este bi/T-S > 0

Consideram urmatoare instanta a problemei urnelor:
(b1/(T-S), b2/(T-S),..,bn/(T-S),(T-2S)/(T-S)) = P2. Ea
este obtinuta prin scalarea din intervalul (0,T-S) in
intervalul (0,1) al celor n numere, la care se adauga
o cantitate speciala (T-2*S)/(T-S).
T-2*S>0, cf. S<=T/2 si totodata T-2*S<T-S =>
0<(T-2*S)/(T-S)<1.

Observam suma acestor numere este 2.
((b1+b2+..bn)+T-2S)/(T-S) = (2T-2S)/(T-S) = 2. Asta
implica ca rezultatul problemei P2 este >= 2. (Sunt
necesare minim 2 urne unitare).

Afirmam ca PROBLEMA P1 ADMITE SOLUTIE DACA SI NUMAI
DACA REZULTATUL PROBLEMEI P2 ESTE 2.
Am aratat ca rezlutatul lui P2 este >=2.

(i) Aratam ca daca problema P1 admite solutie atunci
rez. P2 este 2.

 Daca suma S este obtinubila atunci plasam intr-o urna
numerele a caror suma da S/(T-S)
(bk1/(T-S),bk2/(T-S),...) impreuna cu numarul
(T-2*S)/(T-S), umpland astfel urna. Raman astfel
numere a caror suma este fix (T-S)/(T-S). (Daca suma S
este obtinubila si suma T-S este obtinubila).

 |T-2S| |   |
 |----| |   |
 | S  | |T-S|
 |----| |---|

(ii) Aratam ca daca rez. lui P2 este 2 atunci P1
admite solutie

 Cum in cazul in care rezultatul lui P2 este 2 ambele
urne sunt pline => sigur intr-o urna sunt numere (din
b1/(T-S), b2/T-S, ...) care dau suma (T-S)/(T-S) deci
exista bk1 + bk2 +..+bki = T-S deci P1 admite solutie.

(iii) Aratam ca daca P1 nu admite solutie rez. lui P2
este > 2.

Aratam ca exista cel putin o urna care nu este plina.
Intr-una din urne se va gasi numarul (T-2S)/(T-S).
Pentru ca aceasta urna sa fie plina ar trebui sa
existe numere din (b1/(T-S), ...) a caror suma sa fie
S/(T-S) adica suma S sa fie obtinubila, contradictie
cu presupunearea ca P1 nu admite solutie.

Cum cel putin o urna nu este plina, presupunand prin
absurd ca solutia lui P2 este 2, atunci suma numerelor
din cele doua urne ar fi s1(<1) + s2(<=1) < 2, absurd.

Am demonstrat astfel ca PROBLEMA P1 ADMITE SOLUTIE
DACA SI NUMAI DACA REZULTATUL PROBLEMEI P2 ESTE 2. 

Cum reducerea de la problema P1 la P2 este realizabila
in timp polinomial si cum P1 este NP-Completa => P2
este NP-COMPLETA.

Mircea