Tekintsük az
természetes számokat úgy, hogy 
. Bizonyítható, hogy létezik I és J diszjunkt indexhalmaz (
) úgy, hogy 
, a kérdés az, hogy meghatározható-e I és J polinomiális időben? Ha eltekintünk a korláttól, akkor biztosan NP teljes a feladat (PARTITION a neve a Garey, Johnson-ban).Néha ijesztő, hogy ilyen egyszerű feladatokhoz sem ismerünk jó megoldásokat.
UPDATE. Kicsit még gondolkodtam a dolgon. Szóval a galamblyuk elvvel tényleg könnyű bizonyítani, hogy kell létezzen két olyan részhalmaza a számoknak, amelyeknek egyenlő az összege, de a bizonyításból az is következik, hogy a két részhalmaz egyesítése nem kell kiadja a teljes halmazt, valamint a számok szigorúan pozitívak kell legyenek. Egy n elemű halmaznak
részhalmaza van, de ezek egyike az üreshalmaz, szóval legfönnebb 
féle összeget írhatunk fel az elemekből. Na most ha az elemek összege szigorúan kisebb mint akkor két lehetséges részhalmaznak kötelezően ugyanaz kell legyen az összege, vagyis ugyanabba a galamblyukba kell essen. Ettől ez még egy baromi nehéz feladat, van wiki oldala is, remélem mostmár legalább sikerült helyesen leírni.
4 megjegyzés:
Ijesztő, eddig egyetértünk :)
Megnézném magamnak azt a bizonyítást. Addig ok, hogy 2^n-1=SUM(2^x, x=0...n-1), de a kisebb egyenlő reláció.. utána kell néznem! De ha van link, örömmel venném.
Na igen, szóval elrontottam, ugyanis szigorúan kissebb kell legyen a számok összege mint 2^n-1, mászrészt kicsit gyanus ez az I és J, azt kifelejtettem, hogy diszjunktak kell legyenek, viszont még így is problematikus a dolog, mert szerintem n=4-re és 1,2,3,7 számokra nem teljesül a dolog. Szóval megpróbálok még utána olvasni.
Geeks
Megjegyzés küldése