Demando P = NP

la problemo en informadiko pri ĉu la komplikoklaso P, kiu estas subklaso de la komplikoklaso NP, fakte egalas NP
Estas neniuj versioj de ĉi tiu paĝo, do ĝi eble ne estis kvalite kontrolita.

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

Figuro de komplikecaj klasoj se PNP.

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 jesne. 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 PNP, 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.[1]

NP-plena

redakti

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)?[2] Ĝ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

redakti

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   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   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 PNP do ekzisto de problemoj ekster ambaŭ P kaj NP-plena estis trovita de Ladner.[3]

Opinioj

redakti

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.[4]

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.[5]

Plejparto de komputilaj sciencistoj kredas ke PNP. Ŝ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 PNP kaj devus esplori ankaŭ pruvojn de P = NP. Ekzemple, en 2002 ĉi tiuj propozicioj estis faritaj:[5]

"La ĉefa argumento en favoro de PNP estas la tuteca manko de fundamenta progreso en la areo de elĉerpa serĉo. Ĉi tio estas, miaopinie, tre malforta argumento. La spaco de algoritmoj estas tre granda kaj oni estas nur je la komenco de ĝia esplorado. [. . .] La solvado de lasta teoremo de Fermat ankaŭ montras ke tre simplaj demandoj povas esti responditaj nur per tre profundaj teorioj." (Moshe Y. Vardi, Universitato Rice)
"Alfiksado de spekulativo estas ne bona gvido al planado de esploro. Oni devus ĉiam provi ambaŭ direktojn de ĉiu problemo. Antaŭjuĝo kaŭzis famajn matematikistojn al malsukcesi en solvado de famaj problemoj kies solvaĵo estis kontraŭa al iliaj ekspektoj, eĉ kvankam ili ellaboris ĉiujn bezonatajn manierojn." (Anil Nerode, Universitato Cornell)

Konsekvencoj de pruvo

redakti

Unu el la kaŭzoj kial la problemo allogas tiom da atento estas la konsekvencoj de la respondo.

Pruvo de P = NP povas havi svenigantajn praktikajn konsekvencojn, se la pruvo kondukas al kompetentaj manieroj por solvado de iu el la gravaj problemoj en NP. Diversaj NP-plenaj problemoj estas en multaj kampoj. Estas enormaj pozitivaj konsekvencoj kiuj devus sekvi de akordigo de multaj nun matematike kontraŭstaremaj problemoj. Ekzemple, multaj problemoj en operaciesploro estas NP-plenaj, ekzemple iuj specoj de entjera programado, kaj la vojaĝanta komiza problemo. Kompetentaj solvaĵoj al ĉi tiuj problemoj devus havi enormajn implikaciojn por loĝistiko. Multaj aliaj gravaj problemoj, ekzemple iuj problemoj en proteina struktura antaŭdiro estas ankaŭ NP-plenaj;[6]. 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 [7])

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 PNP 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 PNP, multaj el ĉi tiuj movoj de fokusoj de esploro jam estas faritaj.[8]

Rezultoj pri malfacileco de la pruvo

redakti

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 PNP:

  • 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 PNP por aliaj orakoloj.[9] 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 PNP 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.[10]

Ĉ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

redakti

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ŭ

redakti

Referencoj

redakti
  1. Scott Aaronson. Komplikeca zoo: FP. "FP = FNP se kaj nur se P = NP". http://qwiki.stanford.edu/wiki/Complexity_Zoo#fp Arkivigite je 2010-07-26 per la retarkivo Wayback Machine
  2. . Alirita 2007-08-27 .
  3. R. E. Ladner "Sur la strukturo de polinoma tempo reducibility," J.ACM, 22, pp. 151–171, 1975. Korolario 1.1. ACM.
  4. . Alirita 2008-01-12 .
  5. 5,0 5,1 William I. Gasarch (Junio 2002). “The P=?NP poll. - La P=?NP baloto”, SIGACT News - SIGACT novaĵoj 33 (2), p. 34–47. doi:10.1145/1052796.1052804. 
  6. Berger B, Leighton T - (1998). “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete - Proteino faldado en la HP modelo estas NP-plena”, J. Comput. Biol. 5 (1), p. 27–40. doi:10.1145/1052796.1052804. pmid 9541869. 
  7. . Alirita 2007-08-27 .
  8. L. R. Foulds (OCT., 1983). “The Heuristic Problem-Solving Approach - La heŭristika problemo-solvada maniero”, The Journal of the Operational Research Society - La ĵurnalo de la operacia esplora socio 34 (10), p. pp. 927–934. doi:10.2307/2580891. 
  9. T. P. Baker, J. Gill, R. Solovay. Relativigo de la P = NP demando. SIAM ĵurnalo pri komputado, 4(4): 431-442 (1975)
  10. S. Aaronson kaj A. Wigderson. Algebrigo: Nova barilo en komplikeca teorio, en paperoj de ACM STOC'2008, pp. 731-740.

Eksteraj ligiloj

redakti