Demando P = NP

eta|250px|Figuro de komplikecaj klasoj se **P** ≠ **NP**.

La interrilato inter la rultempaj komplikecaj klasoj **P** kaj **NP** estas nesolvita demando en komputa komplikteorio.

En esenco la demando ĉu **P** = **NP** estas jena: se *jes*-respondo al decida problemo povas esti *kontrolita* en polinoma tempo, ĉu la respondo povas ankaŭ esti *komputita* en polinoma tempo?

Decida problemo estas problemo kun respondo *jes* aŭ *ne*. Solvado estas en polinoma tempo se ĝi estas farata en maksimume *c·nk* paŝoj, kie *n* estas longo de la enigo kaj *k* kaj *c* estas konstantoj sendependaj de la enigo.

Konsideru, ekzemple, la subaran suman problemon, kiu estas ekzemplo de problemo kiu estas *facila* al kontroli, sed kiu estas *kredita* (sed ne *pruvita*) al esti *malfacila* al komputi. Por donita aro de entjeroj, ĉu estas iu nemalplena subaro de ĝi kies sumo estas 0? La problemo estas decida problemo ĉar la respondo estas *jes* (la subaro ekzistas) aŭ *ne* (ne ekzistas). Ekzemple, ĉu estas subaro de la aro {−2, −3, 15, 14, 7, −10} kies sumo estas 0? La respondo estas jesa en ĉi tio okazo, ĉar (−2)+(−3)+15+(−10)=0. Ĝi povas esti rapide kontrolita per kelkaj adicioj. Tamen, trovado de ĉi tia subaro povas preni multe pli longan tempon. La informo bezonata por kontroli pozitivan respondon estas ankaŭ nomata kiel *dokumento*. Kun donita ĝusta dokumento, la jesa respondo al la problemo povas esti kontrolita en polinoma tempo, tiel la problemo estas en **NP**.

La demando ĉu **P** = **NP** demando devas difini ĉu problemoj similaj al la subara suma problemo estas *facile* (en polinoma tempo) komputeblaj. Se **P** ≠ **NP**, do iuj **NP** problemoj estas signife "pli pezaj" por komputi ol por kontroli.

La limigo al jes/ne problemoj estas negrava; la rezultanta problemo kun pli komplika respondo estas permesata, la demando ĉu **FP** = **FNP** estas ekvivalenta al ĉu **P** = **NP**.

## NP-plena 
Por ataki la **P** = **NP** demandon, la koncepto de **NP**-pleneco estas tre utila. La plenaj problemoj de klaso **NP** estas la plej malfacilaj problemoj en **NP** en la senco ke ili estas la aĵoj plej verŝajne ne apartenantaj al **P**. **NP**-plenaj problemoj estas tiuj **NP**-pezaj problemoj kiu estas en **NP**, kie **NP**-pezaj problemoj estas tiuj al kiuj *ĉiu* problemo en **NP** povas reduktiĝi en polinoma tempo. Ekzemple, la decida problema versio de la problemo pri vojaĝanta komizo estas **NP**-plena, tiel *ĉiu* apero de *ĉiu* problemo en **NP** povas esti konvertita mekanike en aperon de la problemo pri vojaĝa komizo, en polinoma tempo. La problemo pri vojaĝanta komizo estas unu el multaj ĉi tiaj **NP**-plenaj problemoj. Se iu **NP**-plena problemo estas en **P**, do **P** = **NP**. Tamen, multaj gravaj problemoj estas montritaj al esti **NP**-plenaj kaj kiel en 2008, neniu polinomo-tempa algoritmo por iu el ili estas sciata.

Surbaze nur de la difino, ne evidentas ke **NP**-plenaj problemoj ekzistas. Bagatela kaj artifika **NP**-plena problemo povas esti formulita tiel: por donita priskribo de maŝino de Turing *M* kiu estas garantiita al halti en polinoma tempo, ĉu ekzistas polinomo-ampleksa enigo kiun *M* akceptas (redonas rezulton *jes*)? Ĝi estas en **NP** ĉar, por donita enigo, estas simple kontroli ĉu *M* akceptas la enigon per simulado de M. Ĝi estas **NP**-peza ĉar la kontrolilo por ĉiu aparta apero de problemo en **NP** povas esti kodita kiel polinomo-tempa maŝino *M* kiu prenas la kontrolatan solvaĵon kiel enigo.

La unua natura problemo pruvita al esti **NP**-plena estis la bulea plenumebloproblemo. Ĉi tiu rezulto
estas sciata kiel teoremo de Cook–Levin. Ĝia pruvo ke la bulea plenumebloproblemo estas NP-plena enhavas teknikajn detalojn pri maŝinoj de Turing kiel ili rilatas al la difino de **NP**. Tamen, post kiam ĉi tiu problemo estis pruvita al esti **NP**-plena, pruvo per malpligrandiĝo provizas pli simplan manieron montradi ke multaj aliaj problemoj estas en ĉi tiu klaso. Tial, vasta klaso de kvazaŭ neinterrilatantaj problemoj estas ĉiuj redukteblaj unu la alian, kaj estas tiel en senco la *sama problemo*.

## Ankoraŭ pli pezaj problemoj 
Kvankam estas nekonate ĉu **P** = **NP**, problemoj ekster **P** estas sciataj. Iuj koncizaj problemoj, tio estas, problemoj kiu operacias ne sur normala enigo sed sur komputa priskribo de la enigo, estas sciata al esti **EKSPTEMPO**-plenaj. Ĉar ĝi povas esti montrite ke **P** \subsetneq **EKSPTEMPO**, ĉi tiuj problemoj estas ekster **P**, kaj tiel postulas pli ol polinoman tempon. Fakte, per la tempa hierarkia teoremo, ili ne povas esti solvitaj en grave malpli granda tempo ol eksponenta tempo.

La problemo de kontrolado vereco de frazo en aritmetiko de Presburger postulas eĉ pli grandan tempon. Fischer kaj Michael O. Rabin pruvis en 1974 ke ĉiu algoritmo kiu kontrolas la verecon de frazoj de Presburger havas rultempon de minimume 2^{2^{cn}} por iu konstanto *c* kie *n* estas la longo de la eniga frazo. De ĉi tie, la problemo estas sciata al bezoni pli ol eksponentan tempon. Eĉ pli malfacila estas la nedecideblaj problemoj, tiaj kiel la problemo de halto. Ili ne povas esti plene solvitaj per iu algoritmo, en la senco ke por ĉiu aparta algoritmo estas minimume unu enigo por kiu la algoritmo ne produktas la ĝustan respondon; ĝi produktas la eraran respondon aŭ ruliĝas eterne sen produktado de respondo.

Se **P** ≠ **NP** do ekzisto de problemoj ekster ambaŭ **P** kaj **NP**-plena estis trovita de Ladner.

## Opinioj 
La demando estas konsiderata al esti la plej grava problemo en la kampo. La Matematiko Instituto Clay oferas 1 milion USD premion por la unua korekta pruvo.

En 2002 estas farita pridemandado de opinio pri ĉu **P** egalas al **NP** de 100 esploristoj. 61 kredis la respondo estas nea, 9 kredita la respondo estas jesa, 22 estis necertaj, kaj 8 kredis ke la demando povas esti sendependa de la nun akceptitaj aksiomoj, kaj tiel neeblas pruvi aŭ malpruvi ĝin.

Plejparto de komputilaj sciencistoj kredas ke **P** ≠ **NP**. Ŝlosila kaŭzo por ĉi tiu konvinko estas ke post jardekoj da studado de la afero, ne estas trovita polinomo-tempa algoritmo por iu **NP**-peza problemo. Ĉi tiuj algoritmoj estis serĉitaj longe antaŭ kiam la koncepto de **NP**-pleneco estis inventita. Ĉiuj el listo de 21 NP-plenaj problemoj de Karp estis jam konataj al tempo de invento de koncepto de **NP**-pleneco. Plue, la rezulto **P** = **NP** devus enhavi multajn aliajn rezultojn kiuj estas nun kreditaj al esti malveraj, ekzemple tion ke **NP** = **co-NP** kaj **P** = **PH**.

Estas ankaŭ intuicie argumentite ke la ekzisto de problemoj kiuj estas pezaj al solvi sed por kiuj la solvaĵoj estas facilaj al kontroli koincidas kun reala monda sperto.

Aliflanke, iuj esploristoj kredas ke oni tro kredas al **P** ≠ **NP** kaj devus esplori ankaŭ pruvojn de **P** = **NP**. Ekzemple, en 2002 ĉi tiuj propozicioj estis faritaj:. Se ĉi tiuj problemoj estis solveblaj kompetente rezultiĝas konsiderebla antaŭenigo en biologio.

De la alia flanko trovo de kompetentaj algoritmoj por **NP**-plenaj problemoj rompos iujn algoritmojn de ĉifrado, ekzemple multe uzatan RSA.

Sed ĉi tiaj ŝanĝoj estas ne tiel gravoj kompare al revolucio kiun kompetenta maniero por solvado de **NP**-plenaj problemoj devus kaŭzi en matematiko mem.

:"...ĝi devus konverti matematikon per permeso al komputilo al trovi formalan pruvon de ĉiu teoremo kiu havas pruvon de modera longo, pro tio ke formalaj pruvoj povas facile esti agnoskitaj en polinoma tempo. Ekzemplaj problemoj povas bone inkluzivi ĉiujn en la jarmilaj premiaj problemoj." (Stephen Cook )

Matematikistoj pasigas grandan tempodaŭron penante pruvi teoremojn. Maniero kiu estas garantiita al trovi pruvojn al teoremoj, se ĝi ekzisti de "modera" amplekso, devus esence plifaciligi iuj aferojn.

Pruvo kiu montras ke **P** ≠ **NP** ne donas praktikajn komputajn bonaĵojn malsimile al pruvo ke **P** = **NP**. Tamen ankaŭ pruvo de **P** ≠ '*NP* devas prezenti grandan antaŭenigon en komputa komplikteorio kaj provizi gvidadon por estontaj esploroj. Ĝi devus permesi montri en formala vojo ke multaj komunaj problemoj ne povas esti solvitaj kompetente, tiel ke la atento de esploristoj povas esti fokusita sur partaj solvaĵoj aŭ solvaĵoj de aliaj problemoj. Pro vasta konvinko ke **P** ≠ **NP**, multaj el ĉi tiuj movoj de fokusoj de esploro jam estas faritaj.

## Rezultoj pri malfacileco de la pruvo 
Grandega kvanto de dediĉita esploro sen esencaj rezultoj sugestas ke la problemo estas malfacila. Fakte, iu el la plej fruktodonaj esploroj rilatantaj al ĉu **P** = **NP** estas en montrado ke ekzistantaj pruvaj teknikoj estas ne povaj sufiĉe por respondi al la demando, tial sugestante ke la novaj manieroj estas verŝajne bezonataj.

Esence ĉiuj sciataj pruvaj teknikoj en komputa komplikteorio estas de unu el la sekvaj klasifikaĵoj, kaj ĉiuj estas sciataj al esti nesufiĉaj por pruvi ke **P** ≠ **NP**:

* **Relativigaj pruvoj:** Imagi mondon kie al ĉiu algoritmo estas permesite fari demandojn al iu fiksita proceduro (subprogramo nomata kiel orakolo, kaj la rula tempo de la orakolo estas neglekteble malgranda kompare al rula tempo de la algoritmo. Plejparto de pruvoj, aparte klasikaj aĵoj, aplikas unuforme en mondo kun orakoloj, sendistinge de kion la orakolo faras. En 1975, T. P. Baker, J. Gill kaj R. Solovay montris ke **P** = **NP** kun respekto al iuj orakoloj, sed **P** ≠ **NP** por aliaj orakoloj. Pro tio ke relativigaj pruvoj povas nur pruvi frazojn kiuj estas unuforme veraj kun respekto al ĉiuj eblaj orakoloj, ĉi tio montris ke relativigaj teknikoj ne povas malkomponi demandon **P** = **NP**.

* **Naturaj pruvoj:** En 1993, Aleksander Razborov kaj Steven Rudich difinis ĝeneralan klason de pruvaj teknikoj por cirkvitaj komplikecaj subaj baroj, nomatan kiel *naturaj pruvoj*. Je la tempo, ĉiuj antaŭe sciataj cirkvitaj subaj baroj estis naturaj, kaj cirkvita komplikeco estis konsiderita kiel tre promesanta maniero por demando pri **P** = **NP**. Tamen, Razborov kaj Rudich montris ke por ke pruvi **P** ≠ **NP** uzante naturan pruvon, oni bezone devas ankaŭ pruvi eĉ pli fortan frazon, kiu estas kredita al esti malvera. Tial estas malverŝajne ke naturaj pruvoj solaj povas malkomponi demandon pri **P** = **NP**.

* **Algebrigaj pruvoj:** Post la rezulto de T. P. Baker, J. Gill kaj R. Solovay, nova nerelativigaj pruvaj teknikoj estis sukcese uzataj por pruvi ke **IP** = **PSPACO**. Tamen, en 2008, Aaronson kaj Wigderson montris ke la ĉefa nova teknika laborilo uzata en la **IP** = **PSPACO** pruvo, kiun ili nomas kiel *algebrigo*, estas nesufiĉa al malkomponi demandon pri **P** = **NP**.

Ĉi tiuj bariloj estas alia kaŭzo kial **NP**-plena problemoj estas utilaj: se polinomo-tempa algoritmo povas esti montrita por **NP**-plena problemo, ĉi tio devus solvi la **P** = **NP** demandon kvazaŭ tiu estas inkluzivita per la pli supraj rezultoj.

## Polinomo-tempaj algoritmoj 
Ne estas sciata ĉu polinomo-tempaj algoritmoj ekzisti por **NP**-plenaj lingvoj. Sed se tiaj algoritmoj ekzistas, iu el ili estas jam sciata. Ekzemple, jena algoritmo de Levin korekte akceptas **NP**-plenan lingvon, sed kiel de 2008, estas nekonate kiel longan rultempon ĝi prenas ĝenerale.

 // Algoritmo kiu akceptas la NP-plenan lingvo SUBARO-SUMO.
 //
 // Ĉi tiu estas polinomo-tempa algoritmo se kaj nur se **P**=**NP**.
 //
 // "Polinomo-tempa" signifas ke ĝi redonas rezulton *jes* en polinoma tempo kam se
 // la respondo devus esti "jes", kaj ruliĝas eterne se ĝi estas "ne".
 //
 // Enigo: S = finia aro de entjeroj
 // Eligo: *jes* se iu subaro de S sumiĝas al 0.
 // Ruliĝas eterne sen eligo alie.
 // Programo de nombro P estas la programo ricevita per
 // skribo de entjero P en duuma sistemo, tiam
 // konsiderado de ĝi kiel linio de bitoj al esti
 // programo. Ĉiu ebla programo povas esti
 // generita tiamaniere, kvankam plejparto el ili faras nenion
 // sencan pro sintaksaj eraroj.
 POR N = 1...malfinio
     POR P = 1...N
         Kuri programan nombro P por N paŝoj kun enigo S
             SE la programo eligas liston de malsamaj entjeroj
                 KAJ la entjeroj estas ĉiuj en S
                 KAJ la entjeroj sumiĝas al 0
             DO
                 ELIGO "jes"
                 HALTO

Se kaj nur se **P** = **NP** ĉi tio estas polinomo-tempa algoritmo akceptanta **NP**-plenan lingvon. "Akceptanta" signifas ke ĝi donas *jes*-respondojn en polinoma tempo, sed estas permesita al kuri eterne kiam la respondo estas nea.

Diferenco inter *solvi* la problemon kaj *akcepti* la lingvon. estas en tio ke la solvanta algoritmo devas ĉiam halti kaj redoni jesas aŭ nean respondon. Kiel en 2008, ĝi estas nekonate ĉu ekzistas algoritmo kiu solvas la problemon en polinoma tempo. Sed se estas algoritmo kiu verŝajne faras ĉi tion en polinoma tempo, do ĉi tia algoritmo estas ricevita per anstataŭigo de la "SE" en la pli supra algoritmo per ĉi tio:

             SE la programo eligas plenan pruvon
                 KAJ ĉiu paŝi de la pruvo estas vera
                 KAJ la konkludo estas ke S havas aŭ ne havas subaro sumantan al 0
             DO
                 ELIGO "jes"aŭ "ne" respektive
                 HALTO

## Vidu ankaŭ 
* Komputada tempo
* **P** (komplikeco)
* **NP** (komplikeco)
* **NP**-plena
* **NP**-peza
* Listo de komplikecaj klasoj
* Nombregoj#Komputiloj kaj komputa komplikeco - iuj pritaksoj de tempoj de kalkulado
* Luda komplikeco
* Listo de malfermitaj problemoj en komputiko
* Nesolvitaj problemoj en matematiko
* Primeco-testo
* Entjera faktorigo

## Referencoj 
## Eksteraj ligiloj 
* Jarmilaj premiaj problemoj 
* Oficiala priskribo de la problemo 
* Ian Stewart sur Minesweeper pri **NP**-pleneco 
* Gerhard J. Woeginger. La P-kontraŭ-NP paĝo. Listo de ligiloj al proponitaj solvaĵoj al la problemo. Iu el ĉi tiuj ligoj statas ke P = NP, iuj ke P ≠ NP. Verŝajna ĉi ĉiuj solvaĵoj estas malĝustaj.
* Komputa komplikeco de ludoj kaj enigmoj
* Komplikeca zoo de Scott Aaronson P , NP 
* Qeden , vikio kiu celas al solvi la jarmilaj premiaj problemoj ("suben por konservado" kiel de 15-a de Julio de 2008)
* Blogo de Scott Aaronson: kaŭzoj al kredi, listo de pliĝustigoj por la konvinko ke P ≠ NP

Kategorio:Komputa komplikeco
Kategorio:Konjektoj
Kategorio:Nesolvitaj problemoj en matematiko
Kategorio:Nesolvitaj problemoj en komputiko