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 . 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 ∀L' en NP, . 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 redakti
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 redakti
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.