Problemă parțială a sumelor

Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor . Urmați sfaturile de proiectare de referință .

Această intrare pe tema matematicii este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia . Urmați sfaturile de proiectare de referință .

Problema sumelor parțiale este una dintre problemele NP-complete . Constă în a determina, având în vedere un set finit de numere întregi , dacă există un subset astfel încât suma elementelor sale să fie ${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">0</span></span>}}${\ displaystyle 0} . Se poate vedea că este ușor să se determine dacă un subset este sau nu soluția problemei, dar nu se cunoaște nicio metodă pentru a găsi o soluție care este semnificativ mai rapidă decât încercarea tuturor subseturilor posibile, cu excepția celor două care conțin toate numerele concordante (toate negative sau toate pozitive), cele formate dintr-un singur număr negativ și de toate numerele pozitive mai mari în valoare absolută decât numărul negativ și cele formate dintr-un singur număr pozitiv și toate numerele negative mai mari în valoare absolută decât numărul pozitiv. Descoperirea unei metode „rapide” pentru a rezolva această problemă ar oferi, de asemenea, soluția uneia dintre problemele mileniului ( P vs NP , formulată de Stephen Cook și Leonid Levin în 1971), pentru care institutul Clay Mathematics a pus la punct. un milion de dolari.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică