NP-peza

En komputa komplikteorio, **NP-peza** (Ne-determina Polinomo-tempo peza) nomas la klason de decidaj problemoj, kiu enhavas ĉiujn problemojn *H*, tia, ke por ĉiu decida problemo *L* en **NP** ekzistas polinom-tempa multaj-unu malpligrandiĝo al *H*, skribata kiel L \leq_p H. Neformale, ĉi tiu klaso povas esti priskribita kiel enhavanta la decidajn problemojn, kiuj estas "almenaŭ kiel peza kiel problemoj en NP". Ĉi tiu intuicio estas subtenata per la fakto, ke se ni povas trovi algoritmon *A*, kiu solvas unu el ĉi tiuj problemoj *H* en polinoma tempo, ni povas konstrui polinom-tempan algoritmon por ĉiu problemo *L* en **NP** per unue plenumo de la malpligrandiĝo de *L* al *H* kaj tiam ruligo la algoritmo *A*.

Do, formale, lingvo *L* estas NP-peza se &forall;L' en **NP**, L' \leq_p L. Se ĝi estas ankaŭ la kazo, ke *L* estas en **NP**, tiam *L* estas **NP-plena**.

La nocio de **NP**-dureco ludas gravan rolon en la diskuto pri la interrilato inter la kompleksecaj klasoj P kaj NP. La klaso **NP-peza** povas esti komprenita kiel la klaso de problemoj, kiuj estas NP-plenaj aŭ pli pezaj.

Komuna eraro estas, pensi, ke la "NP" en "NP-peza" staras por "ne-polinomo". Kvankam ĝi estas larĝe suspektite, ke ne estas polinomo-tempaj algoritmoj por ĉi tiuj problemoj, tio ne estis pruvita.

## Ekzemploj 
Ekzemplo de NP-peza problemo estas la decid-problemo subara suma problemo kiu estas ĉi tiu: donita aro de entjeroj, ĉu iu ne malplena subaro de ili adiciiĝi al nulo?  Tio estas *jes*/*ne* demando, kaj okazas esti NP-kompleta.

Estas ankaŭ decid-problemoj, kiuj estas **NP-pezaj** sed ne **NP-plenaj**, ekzemple la problemo de haltado. Ĉi tiu estas la problemo "donita programo kaj ĝia enigo, ĉu ĝi kuros eterne?" Tio estas *jes*/*ne* demando, do, estas decid-problemo. Estas facile pruvi, ke la problemo de haltado estas **NP-peza** sed ne **NP-plena**. Ekzemple la bulea problemo pri kontentigebleco povas reduktiĝi al la problemo de haltado per tio konverti ĝin al la priskribo de maŝino de Turing, kiu provas ĉiun vervalorajn asignoj kaj kiam ĝi trovas tiun, kiu kontentigas la formulon ĝi haltas, kaj alie ĝi iras en malfinia ciklo. Estas ankaŭ facile vidi, ke la problemo de haltado ne estas en **NP**, ĉar ĉiuj problemoj en NP estas decideblaj kaj la problemo de haltado ne estas.

## Alternativoj difinoj 
Alternativa difino de **NP-peza** ofte uzata limigas **NP-peza** al decid-problemoj, kaj tiam uzas polinom-tempa multaj-unu malpligrandiĝo anstataŭ polinomo-tempan turing-an rabaton. Ĉi tiu nocio de **NP-pezeco** povas esti formulita por funkciaj problemoj kaj ne nur por decid-problemoj.

En ĉi tiu senco, la problemo H estas **NP-peza** se kaj nur se ĉiu decid-problemo L en **NP** povas esti solvita en polinoma tempo per orakola maŝino kun orakolo por H. (Neformale ni povas pensi pri tia maŝino kiel algoritmo, kiu povas voki subprogramon por solvi H kaj solvas L en polinoma tempo se la subprogramo vokita prenas nur unu paŝon por komputi.) Se ni trovos polinomo-tempan algoritmon por iu **NP-peza** problemo tiam ni havos polinomo-tempan algoritmon por ĉiuj problemoj en **NP-facila** kaj ja por ĉiuj problemoj en **NP**).

Ĉu ĉi tiu difino de **NP-facileco** estas ekvivalenta al la unu ĉe la komenco de ĉi-artikolo (por la okazo de decid-problemoj) estas ankoraŭ malfermita problemo kaj estas diskutata en pli detale en la artikolo pri NP-pleneco.

Kategorio:Komputa komplikeco