La P kontraŭ NP-problemo estas grava neklarigita problemo en komputado.
Ĝi demandas ke ĉu ĉiu problemo kies solvo povas esti rapide konfirmita (teknike, konfirmita en polinoma tempo) ankaŭ povas solvita rapide (denove, en polinoma tempo).
#000001
La subestaj temoj unue estis diskutitaj en la 1950-aj jaroj, en leteroj de John Forbes Nash Jr. ĝis la National Security Agency, kaj de Kurt Gödel ĝis John von Neumann.
La preciza deklaro de la P kontraŭ NP-problemo estis lanĉita en 1971 fare de Stephen Cook en lia pionira artikolo "The complexity of theorem proving procedures (La komplekseco de teoremo pruvanta procedurojn)" [2] kaj laŭ multaj estas la plej grava malferma problemo en la kampo.
Ĝi estas unu el la sep Jarmilo-premio-problemoj selektitaj fare de la Argilo-Matematiko-Instituto por porti 1,000,000 USUS$ premio por la unua ĝusta solvo.
#000002
La neformala esprimo rapide, uzita supre, signifas la ekziston de algoritmo solvanta la taskon kiu kuras en polinoma tempo, tia ke la tempo kompletigi la taskon varias kiel polinomfunkcio sur la grandeco de la enigaĵo al la algoritmo (kontraste al, ekzemple, eksponenta tempo).
La ĝenerala klaso de demandoj por kiu iu algoritmo povas disponigi respondon en polinoma tempo estas nomita "klaso P " aŭ ĵus" P ".
Por kelkaj demandoj, ekzistas neniu konata maniero trovi respondon rapide, sed se tia estas provizita per informmontrado kio la respondo estas, estas eble konfirmi la respondon rapide.
La klaso de demandoj por kiu respondo povas esti konfirmita en polinoma tempo estas nomita NP , kiu staras por "nedeterminisma polinoma tempo".
#000003
Respondo al la P = NP- demando determinus ĉu problemoj kiuj povas esti konfirmitaj en polinoma tempo, kiel Sudoko, ankaŭ povas esti solvitaj en polinoma tempo.
Se ĝi turnus tiun P ≠ NP, ĝi signifus ke ekzistas problemoj en NP ol kiuj estas pli malfacilaj komputi por konfirmi: ili ne povus esti solvitaj en polinoma tempo, sed la respondo povus esti konfirmita en polinoma tempo.
#000005
Krom esti grava problemo en komputilteorio, pruvo ambaŭ manieroj havus profundajn implicojn por matematiko, kriptografion, algoritmesploradon, artefaritan inteligentecon, ludoteorion, multmedian pretigon, filozofion, ekonomikon kaj multaijn aliajn kampojn.
#000006
2 Ankoraŭ pli pezaj problemoj
5 Rezultoj pri malfacileco de la pruvo
#000008
Kvankam la P kontraŭ NP- problemo estis formale difinita en 1971, ekzistis antaŭaj sentoj de la problemoj implikitaj, la malfacileco de pruvo, kaj la eblaj sekvoj.
En 1955, matematikisto John Nash skribis leteron al la NSA, kie li konjektis ke fendi sufiĉe kompleksan kodon postulus tempeksponenton en la longo de la ŝlosilo.
Se pruvite (kaj Nash estis konvene skeptika) tio implicus kion ni hodiaŭ nomus P ≠ NP, ĉar proponita ŝlosilo povas facile esti konfirmita en polinoma tempo.
Alia mencio de la subesta problemo okazis en letero (1956) skribita fare de Kurt Gödel al John von Neumann.
Gödel demandis ĉu teoremo-testo (nun povas ko-Np-kompleta) povus esti solvita en kvadrata aŭ lineara tempo, [6] kaj indikis unu el la plej gravaj sekvoj - kiu se tiel, tiam la eltrovo de matematikaj pruvoj povis esti aŭtomatigita.
#000009
La rilato inter la kompleksecklasoj P kaj NP estas volita en komputa komplikeco, la parto de la teorio de komputado traktanta la resursojn necesajn dum komputado por solvi antaŭfiksitan problemon.
La plej oftaj resursoj estas tempo (kiom multajn ŝtupojn ĝi prenas por solvi problemon) kaj spaco (kiom multe da memoro ĝi prenas por solvi problemon).
#000010
En tia analizo, modelo de la komputilo por kiu tempon devas esti analizita estas postulata.
Tipe tiaj modeloj supozas ke la komputilo estas determinisma (donita la nunan ŝtaton de la komputilo kaj iujn ajn enigaĵojn, ekzistas nur unu ebla ago kiun la komputilo eble prenos) kaj sinsekva (ĝi prezentas agojn unu- post la alie).
#000011
El tiu teorio, la klaso P konsistas el ĉiuj tiuj decidoproblemoj (difinitaj malsupre) kiuj povas esti solvitaj sur determinisma sinsekva maŝino en kvanto de tempo kiu estas polinomo en la grandeco de la enigaĵo;
la klaso NP konsistas el ĉiuj tiuj decidoproblemoj kies pozitivaj solvoj povas esti konfirmitaj en polinoma tempo donita la dekstrajn informojn, aŭ ekvivalente, kies solvo povas esti trovita en polinoma tempo sur ne-determinisma maŝino.
Verŝajne la plej granda malferma demando en teoria komputiko koncernas la rilaton inter tiuj du klasoj:
#000012
Ĉu P egala al NP estas?
#000013
En balotenketo de 100 esploristoj, (2002) 61 kredis la respondon por esti neniu, 9 kredis ke la respondo estas jes, kaj 22 estis necertaj;
8 kredis ke la demando povas esti sendependa de la nuntempe akceptitaj aksiomoj kaj tial malpruvebla aŭ kontraŭpruvi.
#000014
En 2012, 10 jarojn poste, la sama balotenketo estis ripetita.
La nombro da esploristoj kiuj respondis estis 151: 126 (83%) kredis la respondon por esti neniu, 12 (9%) kredis ke la respondo estas jes, 5 (3%) kredis ke la demando povas esti sendependa de la nuntempe akceptitaj aksiomoj kaj tial malpruvebla aŭ kontraŭpruvi, 8 (5%) diris aŭ ne scias aŭ ne zorgas aŭ ne deziras ke la respondo estu jes nek la problemo esti solvitaj.
#000015
Por ataki la P = NP- demandon, la koncepto de Np-tuteco estas tre utilaj.
Np-kompletaj problemoj estas aro de problemoj al ĉiu el kiuj ĉiu alia Np-problemo povas esti reduktita en polinoma tempo, kaj kies solvo daŭre povas esti konfirmita en polinoma tempo.
Tio estas, ĉiu NP- problemo povas esti transformita en iuj da la Np-kompletajn problemojn.
Neformale, Np-kompleta problemo estas NP- problemo kiu estas almenaŭ same "malfacila" kiel iu alia problemo en NP.
#000016
Np-malmolaj problemoj estas tiuj minimume same forte kiel NP- problemoj, t.e., ĉiuj NP- problemoj povas esti reduktitaj (en polinoma tempo) al ili.
Np-malmolaj problemoj ne devas esti en NP, t.e., ili ne devas havi solvojn konfirmeblaj en polinoma tempo.
#000017
Ekzemple, la bulea plenumebloproblemo estas Np-kompleta de la Kuir-Levin teoremo, tiel ke ĉiu kazo de iu problemo en NP povas esti transformita meĥanike en kazon de la bulea plenumebloproblemo en polinoma tempo.
La bulea plenumebloproblemo estas unu el kvanto tiaj Np-kompletaj problemoj.
Se entute Np-kompleta problemo estas en P, tiam ĝi sekvus tiun P = NP.
Tamen, multaj gravaj problemoj pruviĝis esti Np-kompletaj, kaj neniu rapida algoritmo por iu da ili estas konata.
#000018
Bazite sur la difino sole ĝi ne estas evidenta ke Np-kompletaj problemoj ekzistas;
tamen, sensignifa kaj elpensita Np-kompleta problemo povas esti formulita jene: surbaze de priskribo de maŝino de Turing M garantiita por halti en polinoma tempo, faras tie ekzistu polinom-grandeca enigaĵo kiun tiu M akceptos?
Ĝi estas en NP ĉar (donita enigaĵon) estas simple kontroli ĉu M akceptas la enigaĵon simulante M;
ĝi estas Np-kompleta ĉar la konfirmilo por iu speciala kazo de problemo en NP povas esti ĉifrita kiel polinomtempa maŝino M kiu prenas la solvon por esti konfirmita kiel enigaĵo.
Tiam la demando de ĉu la kazo estas jes aŭ neniu kazo estas determinita per ĉu valida enigaĵo ekzistas.
#000019
La unua natura problemo pruvita por esti Np-kompleta estis la bulea plenumebloproblemo.
Kiel notite supre, tio estas la Kuir-Levin teoremo;
ĝia pruvo ke satisfiabileco estas Np-kompleta enhavas teknikajn detalojn pri maŝino de Turing kiam ili rilatigas al la difino de NP.
Tamen, post kiam tiu problemo estis pruvita por esti Np-kompleta, pruvo per redukto disponigis pli simplan manieron montri ke multaj aliaj problemoj ankaŭ estas Np-kompletaj, inkluzive de la subara sumproblemo diskutita pli frue.
Tiel, vasta klaso de ŝajne senrilataj problemoj estas tute reduktebla unu al la alia, kaj estas en signifo "la sama problemo".
#000020
Kvankam estas nekonate ĉu P = NP, problemoj ekstere de P estas konataj.
Kelkaj trafaj problemoj (problemoj kiuj funkciigas ne sur normala enigaĵo, sed en komputila priskribo de la enigaĵo) povas esti EXPTIME-kompletaj .
Ĉar povas esti montrite ke P ≠ ExPTIME , tiuj problemoj estas ekstere P, kaj tiel postulas pli ol polinoma tempo.
Fakte, de la tempohierarkioteoremo, ili ne povas esti solvitaj en signife malpli ol eksponenta tempo.
Ekzemploj inkludas trovi perfektan strategion por ŝako (sur N × N tabulo) [11] kaj iuj aliaj tabulludoj.
#000021
La problemo de decidado de la vero de deklaro en Presburger-aritmetiko postulas eĉ pli da tempo.
Ĉi tie, n estas la daŭro de la Presburger-deklaro.
Tial, la problemo povas bezoni pli ol eksponenta ruligotempo.
Eĉ pli malfacilaj estas la nedecideblaj problemoj, kiel ekzemple la haltadproblemo.
Ili ne povas esti tute solvitaj per iu algoritmo, en la senco ke por iu speciala algoritmo ekzistas almenaŭ unu enigaĵo por kiu tiu algoritmo ne produktos la ĝustan respondon;
ĝi aŭ produktos la malĝustan respondon, finiĝos sen donado de decida respondo, aŭ alie kuras eterne sen produktado de ajna respondo entute.
#000022
Ĝi estis montrita fare de Ladner kiun se P ≠ NP tiam tie ekzistu problemojn en NP kiuj estas nek en P nek Np-kompletan.
Tiaj problemoj estas nomitaj Np-mezaj problemoj.
La grafea izomorfioproblemo, la diskretlogaritma problemo kaj la faktorigo de entjerproblemo estas ekzemploj de problemoj kreditaj esti Np-mezaj.
Ili estas kelkaj el la tre malmultaj NP- problemoj ne konataj esti en P aŭ esti Np-kompletaj.
#000024
La grafea izomorfioproblemo estas la komputila problemo de determinado ĉu du finhavaj grafeoj estas izomorfaj.
Grava neklarigita problemo en kompleksecteorio estas ĉu la grafea izomorfioproblemo estas en P, Np-kompleta, aŭ Np-meza.
La respondo ne estas konata, sed estas kredite ke la problemo estas almenaŭ ne Np-kompleta.
Se grafeizomorfio estas Np-kompleta, la polinomtempa hierarkio kolapsas al ĝia dua nivela.
Ĉar estas ĝenerale kredite ke la polinomhierarkio ne kolapsas al iu finhava nivelo, estas kredite ke grafeizomorfio ne estas Np-kompleta.
La plej bona algoritmo por tiu problemo, pro László Babai kaj Eugene Luks, havas ruligotempon 2O (√ nlog ( n) por grafeoj kun n verdglacioj.
#000025
La faktorigo de entjerproblemo estas la komputila problemo da determinado de la ĉefa faktorigado de antaŭfiksita entjero.
Vortumita kiel decidoproblemo, ĝi estas la problemo de decidado ĉu la enigaĵo havas faktoron malpli ol k.
Neniu efika faktorigo de entjeralgoritmo estas konata, kaj tiu fakto formas la bazon de pluraj modernaj kriptigaj sistemoj, kiel ekzemple la RSA algoritmo.
La faktorigo de entjerproblemo estas en NP kaj en ko-Np (kaj eĉ en SUPRE kaj ko-UP [16] ).
Se la problemo estas Np-kompleta, la polinomtempa hierarkio kolapsos al ĝia unua nivelo (t.e., NP = ko-Np).
La plej konata algoritmo por faktorigo de entjero estas la ĝenerala numero-kampokribrilo, kiu prenas atendatan tempon
#000026
Tamen, la plej konata kvantumalgoritmo por tiu problemo, la algoritmo de Shor, enrutinigas polinoman tempon, kvankam tio ne indikas kie la problemo kuŝas kun respekto al ne-kvantaj kompleksecklasoj.
#000027
Ĉio el ĉi-supra diskuto supozis ke P signifas "facila" kaj "ne en P " signifas "forte", supozon konatan kiel la disertaĵo de Cobham .
Ĝi estas ofta kaj sufiĉe preciza supozo en kompleksecteorio;
tamen, ĝi havas kelkajn avertrimarkojn.
#000028
Unue, ĝi ne estas ĉiam vera en praktiko.
Teoria polinomalgoritmo povas havi ekstreme grandajn konstantajn faktorojn aŭ eksponentojn tiel igante ĝin nepraktika.
Aliflanke, eĉ se problemo pruviĝas esti Np-kompleta, kaj eĉ se P ≠ NP, povas daŭre ekzisti efikaj aliroj al pritraktado de la problemo en praktiko.
Ekzistas algoritmoj por multaj Np-kompletaj problemoj, kiel ekzemple la tornistroproblemo, la vojaĝantvendista problemo kaj la bulea plenumebloproblemo, kiuj povas solvi al optimeco multajn real-mondajn kazojn en akceptebla tempo.
La empiria mezum-kaza komplekseco (tempo vs. problemgrandeco) de tiaj algoritmoj povas esti surprize malalta.
Ekzemplo estas la simpla algoritmo en linia programado, kiu laboras surprize bone en praktiko;
malgraŭ havado de eksponenta plej malbonkaza polinoma tempo ĝi kuras sur alparo kun la plej konataj polinomtempaj algoritmoj.
#000029
Due, ekzistas specoj de komputadoj kiuj ne harmonias kun la maŝino de Turing-modelo sur kiu P kaj NP estas difinitaj, kiel ekzemple kvantekomputado kaj hazardigitaj algoritmoj.
#000030
Laŭ balotenketoj, [8] [19] la plej multaj komputikistoj kredas tiun P ≠ NP.
Esenca kialo por tiu kredo estas ke post jardekoj de studado de tiuj problemoj neniu povis trovi polinomtempan algoritmon por iuj da pli ol 3000 gravaj konataj Np-kompletaj problemoj (vidu Listo de Np-kompletaj problemoj).
Tiuj algoritmoj estis serĉitaj long antaŭ ol la koncepto de Np-tuteco estis eĉ difinita ( la 21 Np-kompletaj problemoj de Karp, inter la unua trovitaj, estis ĉiuj bonkonataj ekzistantaj problemoj tiutempe kiam ili pruviĝis esti Np-kompletaj).
Krome, la rezulto P = NP implicus multaijn aliajn surprizajn rezultojn kiuj verŝajne nuntempe estas falsaj, kiel ekzemple NP = ko-Np kaj P = PH .
#000031
Estas ankaŭ intuicie argumentite ke la ekzisto de problemoj kiuj estas malmolaj solvi krom por kiujn la solvoj facile konfirmeblas matĉoj real-mondan sperton.
#000032
Aliflanke, kelkaj esploristoj kredas ke ekzistas superoptimismo en kredado de P ≠ NP kaj ke esploristoj devus esplori pruvojn de P = NP ankaŭ.
Ekzemple, en 2002 tiuj deklaroj estis faritaj: [8]
#000034
La ĉefargumento en favoro de P ≠ NP estas la totala manko de fundamenta progreso en la areo de ĝisfunda serĉo.
Tio estas, en mia opinio, tre malforta argumento.
La spaco de algoritmoj estas tre granda kaj ni estas nur komence de ĝia esplorado.
La rezolucio de la lasta teoremo de Fermat ankaŭ montras ke tre facilaj demandoj povas esti solvitaj nur per tre profundaj teorioj.
#000035
Esti alkroĉita al konjekto ne estas bona gvidisto priesplori planadon.
Oni ĉiam devus provi ambaŭ indikojn de ĉiu problemo.
Antaŭjuĝo igis famajn matematikistojn malsukcesi solvi famajn problemojn kies solvo estis kontraŭa al iliaj atendoj, eĉ se ili evoluigis ĉiujn metodojn postulatajn.
#000036
Unu el la kialoj kiujn la problemo altiras tiel al multe da atento estas la sekvoj de la respondo.
Ambaŭ indikoj de rezolucio avancus teorion grandege, kaj eble havus enormajn praktikajn sekvojn ankaŭ.
#000037
Pruvo ke P = NP povus havi impresajn praktikajn sekvojn, se la pruvo kondukas al efikaj metodoj por solvado de kelkajn el la gravaj problemoj en NP.
Estas ankaŭ eble ke pruvo ne kondukus rekte al efikaj metodoj, eble se la pruvo estas ne-helpema, aŭ la grandeco de la salta polinomo estas tro granda por esti efika en praktiko.
La sekvoj, kaj pozitivaj kaj negativaj, ekestas ĉar diversaj Np-kompletaj problemoj estas fundamentaj en multaj kampoj.
#000038
Kriptografio, ekzemple, dependas de certaj problemoj estantaj malfacila.
Helpema kaj efika solvo [Noto 2] al Np-kompleta problemo kiel ekzemple 3-SAT rompus la plej multajn ekzistantajn kriptsistemojn inkluzive de:
#000039
publikŝlosila kriptografio, [21] fundamento por multaj modernaj sekurecaplikoj kiel ekzemple sekuraj financaj transakcioj super la Interreto;
simetriaj ĉifroj kiel ekzemple AES aŭ 3DES, [22] uzitaj por la ĉifrado de komunikaddatenoj.
unudirektaj funkcioj uzite en kriptiga hakado.
La problemon de trovado de antaŭ-bildo kiu hakas al antaŭfiksita valoro [23] devas malfacili esti utila, kaj ideale devus postuli eksponentan tempon.
Tamen, ĉu P NP, tiam trovanta antaŭ-bildon M povas esti finita polinoman tempon, tra redukto al SAT.
#000040
Tiuj devus esti modifitaj aŭ anstataŭigita per informo-teorie sekuraj solvoj ne esence bazite sur P-NP-ekvivalenteco.
#000041
Aliflanke, ekzistas grandegaj pozitivaj sekvoj kiuj sekvus el igado de akordiĝema multaj nuntempe matematike nesolveblaj problemoj.
Ekzemple, multaj problemoj en operacianalizo estas Np-kompletaj, kiel ekzemple kelkaj specoj de entjerprogramado kaj la migranta vendistoproblemo.
Efikaj solvoj al tiuj problemoj havus grandegajn implicojn por loĝistiko.
Multaj aliaj gravaj problemoj, kiel ekzemple kelkaj problemoj en proteinstrukturprognozo, ankaŭ estas Np-kompletaj;
se tiuj problemoj estis efike solveblaj ĝi povus sproni konsiderindajn progresojn en vivsciencoj kaj bioteknologio.
#000042
Sed tiaj ŝanĝoj povas paliĝi en signifo komparite kun la revolucio efika metodo por solvado de Np-kompletaj problemoj kaŭzus en matematiko mem.
Gödel, en liaj fruaj pensoj sur komputadokomplekseco, notis ke mekanika metodo kiu povis solvi ajnan problemon revoluciigus matematikon: [26]
#000043
Se vere ekzistus maŝino kun φ (n) ∼ k ⋅ n (aŭ eĉ ∼ k ⋅ N kun nombro), tio havus sekvojn de la plej granda graveco.
Nome, ĝi evidente signifus tion malgraŭ la undecidabileco de la Entscheidungsproblem, la mensa laboro de matematikisto koncerne Jes-aŭ-neniujn demandojn povus esti tute anstataŭigita per maŝino.
Post ĉio, oni simple devus elekti la naturan pli sensentan n tiel grandan ke kiam la maŝino ne faras rezulton, sonas neniun racie por pensi pli pri la problemo.
#000044
ĝi transformus matematikon permesante al komputilo trovi formalan pruvon de iu teoremo kiu havas pruvon de akceptebla longo, ĉar formalaj pruvoj povas facile esti rekonitaj en polinoma tempo.
Ekzemploproblemoj povas bone inkludi ĉiujn la CMI-premioproblemoj.
#000046
Esplormatematikistoj pasigas siajn karierojn provante pruvi teoremoj, kaj kelkaj pruvoj prenis jardekojn aŭ eĉ jarcentojn por trovi post kiam problemoj estis deklaritaj - ekzemple, la lasta teoremo de Fermat daŭris pli ol tri jarcentojn por pruvi.
Metodo kiu estas garantiita por trovi pruvojn al teoremoj, oni devus ekzisti de "akceptebla" grandeco, esence finus tiun lukton.
#000047
Donald Knuth deklaris ke li kredis ke P = NP, sed estas rezervita koncerne la efikon de ebla pruvo: [29]
#000048
mi ne kredas ke la egaleco P = NP montriĝos por helpema eĉ se ĝi estas pruvita, ĉar tia pruvo preskaŭ certe estos nonkonstruktive.
#000049
Pruvo ke montrita ke P ≠ NP malhavus la praktikajn komputilajn avantaĝojn de pruvo tiu P = NP, sed tamen reprezentus tre signifan antaŭeniĝon en komputa komplikeco kaj disponigus konsiladon por estonta esplorado.
Ĝi permesus unun por montri laŭ formala maniero ke multaj komunaj problemoj ne povas esti solvitaj efike, tiel ke la atento de esploristoj povas esti temigis partajn solvojn aŭ solvojn al aliaj problemoj.
Pro ĝeneraligita kredo je P ≠ NP, multe de tiu enfokusigo de esplorado jam okazis.
#000050
Rezultoj pri malfacileco de pruvo
#000052
Kvankam la P = NP- problemo mem restas malfermaj malgraŭ milion-dolara premio kaj enorma kvanto de diligenta esplorado, laboroj por solvi la problemon kondukis al pluraj novaj teknikoj.
Aparte, iuj el la plej fruktodona esplorado ligita al la P = NP- problemo estis en montrado ke ekzistantaj pruvteknikoj ne estas sufiĉe potencaj por respondi la demandon, tiel sugestante ke romano teknikaj aliroj estu postulataj.
#000053
Kiel kroma indico por la malfacileco de la problemo, esence ĉiuj konataj pruvteknikoj en komputkomplikeca aŭtuno en unu el la post klasifikoj, ĉiu el kiu povas esti nesufiĉa pruvi tiun P ≠ NP:
#000054
Tiuj barieroj estas alia kialo kial Np-kompletaj problemoj estas utilaj: se polinomtempa algoritmo povas esti montrita por Np-kompleta problemo, tio solvus la P = NP- problemo laŭ maniero ne ekskludite per ĉi-supraj rezultoj.
#000055
Tiuj barieroj ankaŭ igis kelkajn komputikistojn sugesti ke la P kontraŭ NP- problemo povas esti sendependa de normaj aksiomsistemoj kiel ZFC (ne povas esti pruvita aŭ kontraŭpruvita ene de ili).
La interpreto de sendependecrezulto povis esti tiel aŭ neniu polinomtempa algoritmo ekzistas por iu Np-kompleta problemo, kaj tia pruvo ne povas esti konstruita en (ekz.) ZFC, aŭ ke polinomtempaj algoritmoj por Np-kompletaj problemoj povas ekzisti, sed estas maleble pruvi en ZFC ke tiaj algoritmoj estas ĝustaj.
Tamen, se ĝi povas esti montrita, uzante teknikojn de la speco kiuj povas nuntempe esti uzeblaj, ke la problemo ne povas esti decidita eĉ kun multe pli malfortaj supozoj etendantaj la Peano-aksiomojn (Patro) por entjeraritmetiko, tiam tie nepre ekzistus preskaŭ-polinomatempaj algoritmoj por ĉiu problemo en NP.
Tial, se oni kredas (ĉar plej multe de la komplekseco teoriuloj faras) ke ne ĉiuj problemoj en NP havas efikajn algoritmojn, ĝi sekvus tiujn pruvojn de sendependeco uzanta tiujn teknikojn ne povas esti ebla.
Plie, tiu rezulto implicas tion pruvantan sendependeco de Patro aŭ ZFC uzanta nuntempe konatajn teknikojn estas al neniu pli facila ol pruvado de la ekzisto de efikaj algoritmoj por ĉiuj problemoj en NP.
#000056
La P = kiun NP- problemo povas esti reproponita laŭ esprimebla certaj klasoj de logikaj deklaroj, kiel rezulto de laboro en priskriba komplekseco.
#000058
Pripensu ĉiujn lingvojn de finhavaj strukturoj kun fiksa signaturo inkluzive de linia ord rilato.
Tiam, tute tiaj lingvoj en P povas esti esprimitaj en unuaorda logiko kun la aldono de taŭga malplej fikspunkto-kombinator.
Efike, tio, en kombinaĵo kun la ordo, permesas la difinon de rekursivaj funkcioj.
Tiel longe kiel la signaturo enhavas almenaŭ unu predikaton aŭ funkcion aldone al la eminenta ordrilato, tiel ke la kvanto de regiono okupita por stoki tiajn finhavajn strukturojn estas fakte polinomo en la nombro da elementoj en la strukturo, tion ĝuste karakterizas P.
#000059
Simile, NP estas la aro de lingvoj esprimeblaj en ekzisteca duaorda logiko - t.e., duaorda logiko malvastanima ekskludi ĉiu-kvantoron super rilatoj, funkcioj, kaj subaroj.
La lingvoj en la polinomhierarkio, PH , egalrilatas al ĉio el duaorda logiko.
Tiel, la demando "estas P kiun bonorda subaro de NP " povas esti reformulita kiel "estas ekzisteca duaorda logiko kapabla priskribi lingvojn (de finhava linie ordigis strukturojn kun nesensignifa signaturo) ke unuaorda logiko kun malplej fikspunkto ne povas?
La vorto "ekzisteca" eĉ povas esti finita de la antaŭa karakterizado, ekde P = NP se kaj nur se P = PH (kiel la unua establus tiun NP = ko-Np, kiu en victurno implicas tion NP = PH).
#000060
Neniu algoritmo por iu Np-kompleta problemo povas kuri en polinoma tempo.
Tamen, ekzistas algoritmoj konataj pro Np-kompletaj problemoj kun la posedaĵo kiun se P = NP, tiam la algoritmo prizorgas en polinoma tempo dum akceptado de kazoj (kvankam kun grandegaj konstantoj, igante la algoritmon nepraktika).
Tamen, tiuj algoritmoj ne kvalifikiĝas kiel polinoma tempo ĉar ilia veturtempo sur malaprobado kazoj ne estas polinomoj.
La sekva algoritmo, pro Levin (sen iu citaĵo), estas tia ekzemplo malsupre.
Ĝi funkcias en polinoma tempo per enigaĵoj kiuj estas en SUBARO-SUMO se kaj nur se P = NP:
#000061
Se, kaj nur se, P = NP, tiam tio estas polinomtempa algoritmo akceptanta Np-kompletan lingvon.
"Akceptante" rimedoj ĝi donas "jes" respondojn en polinoma tempo, sed estas permesitaj kuri eterne kiam la respondo "ne" estas (ankaŭ konata kiel semi-algoritmo).
#000062
Tiu algoritmo estas grandege nepraktika, eĉ se P = NP.
Se la plej mallonga programo kiu povas solvi SUBARO-SUMON en polinoma tempo estas b pecojn longa, ĉi-supra algoritmo provos almenaŭ 2 b −1 aliaj programoj unue.
#000063
Koncipe parolante, decidoproblemo estas problemo kiu prenas kiel enigaĵo iun ŝnuron w super alfabeto σ, kaj produktaĵojn "jes" aŭ "ne".
Se ekzistas algoritmo (diru maŝinon de Turing, aŭ komputilan programon kun nelimigita memoro) kiu povas produkti la ĝustan respondon por iu enigo-literaĵo de longo n en maksimume cnk ŝtupoj, kie k kaj c estas konstantoj sendependaj de la enigo-literaĵo, tiam ni diras ke la problemo povas esti solvita en polinoma tempo kaj ke ni metas ĝin en la klason P.
Formale, P estas difinita kiel la aro de ĉiuj lingvoj kiuj povas esti deciditaj per determinisma polinomtempa maŝino de Turing.
#000064
kaj determinisma polinomtempa maŝino de Turing estas determinisma maŝino de Turing M kiu kontentigas la sekvajn du kondiĉojn:
#000065
M haltoj sur ĉio enir w kaj
#000066
NP povas esti difinita simile uzante nedeterminismajn maŝinon de Turing (la tradiciajn maniero).
Tamen, moderna aliro al difini NP devas utiligi la koncepton de atestilo kaj konfirmilo.
Formale, NP estas difinita kiel la aro de lingvoj super finhava alfabeto kiuj havas konfirmilon kiu kuras en polinoma tempo, kie la nocio de "konfirmilo" estas difinita jene.
#000067
Lasu L esti lingvo super finhava alfabeto, σ.
#000068
Maŝino de Turing kiu decidas Lr estas nomitaj konfirmilo por L kaj y tia ke ( x, y
R estas nomita atestilo pri membreco de x en L.
#000069
Ĝenerale, konfirmilo ne devas esti polinomtempa.
Tamen, por L por esti en NP, devas ekzisti konfirmilo kiu kuras en polinoma tempo.
#000070
Klare, la demando de ĉu fakto x estas kunmetaĵo estas ekvivalenta al la demando de ĉu x estas membro de KUNMETAĴO.
Povas esti montrite ke SINTEXA ∈ NP de konfirmado ke ĝi kontentigas ĉi-supran difinon (se ni identigas naturajn nombrojn kun iliaj binaraj reprezentantaroj).
#000071
Ekzistas multaj ekvivalentaj manieroj priskribi Np-tuteco.
#000072
L estas Np-kompleta se, kaj nur se, la sekvaj du kondiĉoj estas kontentigitaj:
#000074
Alternative, se L ∈ NP, kaj ekzistas alia Np-kompleta problemo kiu povas esti polinomtempa reduktita al L, tiam L estas Np-kompleta.
Tio estas ofta maniero pruvi iu nova problemo estas Np-kompleta.
#000076
Listo de nesolvitaj problemoj en matematiko
#000077
^ A nondeterministic maŝino de Turing can move to a state that is not determined by the previous state.
Such a machine could solve a Np problem in polinoma tempo by falling into the correct answer state (by luck), then conventionally verifying it.
Such machines are not practical for solving realistic problems but can be used as theoretical models.
^ Ekzakte kiel efika solvo devas devi prezenti minacon al kriptografio dependas de la detaloj.
#000078
La interrilato inter la rultempaj komplikecaj klasoj P kaj NP estas nesolvita demando en komputa komplikteorio.
#000082
En esenco la demando ĉu P = NP estas jena: se jes-respondo al decida problemo povas esti kontrolita en polinoma tempo, ĉu la respondo povas ankaŭ esti komputita en polinoma tempo?
#000083
Decida problemo estas problemo kun respondo jes aŭ ne. Solvado estas en polinoma tempo se ĝi estas farata en maksimume c·nk paŝoj, kie n estas longo de la enigo kaj k kaj c estas konstantoj sendependaj de la enigo.
#000084
La demando ĉu P = NP demando devas difini ĉ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.
#000085
La limigo al jes/ne problemoj estas negrava; la rezultanta problemo kun pli komplika respondo estas permesata, la demando ĉu FP = FNP estas ekvivalenta al ĉu P = NP.[1]
#000086
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 aĵoj plej verŝ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 ĉiu problemo en NP povas reduktiĝi en polinoma tempo. Ekzemple, la decida problema versio de la problemo pri vojaĝanta komizo estas NP-plena, tiel ĉiu apero de ĉiu problemo en NP povas esti konvertita mekanike en aperon de la problemo pri vojaĝa komizo, en polinoma tempo. La problemo pri vojaĝanta komizo estas unu el multaj ĉ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.
#000087
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 maŝino de Turing M kiu estas garantiita al halti en polinoma tempo, ĉu ekzistas polinomo-ampleksa enigo kiun M akceptas (redonas rezulton jes)?[2] Ĝi estas en NP ĉar, por donita enigo, estas simple kontroli ĉu M akceptas la enigon per simulado de M. Ĝi estas NP-peza ĉar la kontrolilo por ĉiu aparta apero de problemo en NP povas esti kodita kiel polinomo-tempa maŝino M kiu prenas la kontrolatan solvaĵon kiel enigo.
#000088
La unua natura problemo pruvita al esti NP-plena estis la bulea plenumebloproblemo. Ĉi tiu rezulto estas sciata kiel teoremo de Cook–Levin. Ĝia pruvo ke la bulea plenumebloproblemo estas NP-plena enhavas teknikajn detalojn pri maŝinoj de Turing kiel ili rilatas al la difino de NP. Tamen, post kiam ĉi tiu problemo estis pruvita al esti NP-plena, pruvo per malpligrandiĝo provizas pli simplan manieron montradi ke multaj aliaj problemoj estas en ĉi tiu klaso. Tial, vasta klaso de kvazaŭ neinterrilatantaj problemoj estas ĉiuj redukteblaj unu la alian, kaj estas tiel en senso la sama problemo.
#000089
Kvankam estas nekonate ĉ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. Ĉar ĝi povas esti montrite ke P EKSPTEMPO, ĉ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.
#000090
La problemo de kontrolado vereco de frazo en aritmetiko de Presburger postulas eĉ pli grandan tempon. Fischer kaj Michael O. Rabin pruvis en 1974 ke ĉ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 ĉi tie, la problemo estas sciata al bezoni pli ol eksponentan tempon. Eĉ pli malfacila estas la nedecideblaj problemoj, tiaj kiel la problemo de halto. Ili ne povas esti plene solvitaj per iu algoritmo, en la senso ke por ĉiu aparta algoritmo estas minimume unu enigo por kiu la algoritmo ne produktas la ĝustan respondon; ĝi produktas la eraran respondon aŭ ruliĝas eterne sen produktado de respondo.
#000091
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]
#000093
En 2002 estas farita pridemandado de opinio pri ĉ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 aŭ malpruvi ĝin.[5]
#000094
Plejparo de komputilaj sciencistoj kredas ke P ≠ NP. Ŝlosila kaŭzo por ĉi tiu konvinko estas ke post jardekoj da studado de la afero, ne estas trovita polinomo-tempa algoritmo por iu NP-peza problemo. Ĉi tiuj algoritmoj estis serĉitaj longe antaŭ kiam la koncepto de NP-pleneco estis inventita. Ĉ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.
#000095
Estas ankaŭ intuicie argumentite ke la ekzisto de problemoj kiuj estas pezaj al solvi sed por kiuj la solvaĵoj estas facilaj al kontroli koincidas kun reala monda sperto.
#000096
Aliflanke, iuj esploristoj kredas ke oni tro kredas al P ≠ NP kaj devus esplori ankaŭ pruvojn de P = NP. Ekzemple, en 2002 ĉi tiuj propozicioj estis faritaj:[5]
#000097
"La ĉefa argumento en favoro de P ≠ NP estas la tuteca manko de fundamenta progreso en la areo de elĉerpa serĉo. Ĉi tio estas, miaopinie, tre malforta argumento. La spaco de algoritmoj estas tre granda kaj oni estas nur je la komenco de ĝia esplorado. [. . .] La solvado de lasta teoremo de Fermat ankaŭ 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 ĉiam provi ambaŭ direktojn de ĉiu problemo. Antaŭjuĝo kaŭzis famajn matematikistojn al malsukcesi en solvado de famaj problemoj kies solvaĵo estis kontraŭa al iliaj ekspektoj, eĉ kvankam ili ellaboris ĉiujn bezonatajn manierojn." (Anil Nerode, Universitato Cornell)
#000098
"La ĉefa argumento en favoro de P ≠ NP estas la tuteca manko de fundamenta progreso en la areo de elĉerpa serĉo. Ĉi tio estas, miaopinie, tre malforta argumento. La spaco de algoritmoj estas tre granda kaj oni estas nur je la komenco de ĝia esplorado. [. . .] La solvado de lasta teoremo de Fermat ankaŭ montras ke tre simplaj demandoj povas esti responditaj nur per tre profundaj teorioj." (Moshe Y. Vardi, Universitato Rice)
#000099
"Alfiksado de spekulativo estas ne bona gvido al planado de esploro. Oni devus ĉiam provi ambaŭ direktojn de ĉiu problemo. Antaŭjuĝo kaŭzis famajn matematikistojn al malsukcesi en solvado de famaj problemoj kies solvaĵo estis kontraŭa al iliaj ekspektoj, eĉ kvankam ili ellaboris ĉiujn bezonatajn manierojn." (Anil Nerode, Universitato Cornell)
#000100
Unu el la kaŭzoj kial la problemo allogas tiom da atento estas la konsekvencoj de la respondo.
#000101
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 kontraŭstaremaj problemoj. Ekzemple, multaj problemoj en operaciesploro estas NP-plenaj, ekzemple iuj specoj de entjera programado, kaj la vojaĝanta komiza problemo. Kompetentaj solvaĵoj al ĉi tiuj problemoj devus havi enormajn implikaciojn por loĝistiko. Multaj aliaj gravaj problemoj, ekzemple iuj problemoj en proteina struktura antaŭdiro estas ankaŭ NP-plenaj;[6]. Se ĉi tiuj problemoj estis solveblaj kompetente rezultiĝas konsiderebla antaŭenigo en biologio.
#000102
De la alia flanko trovo de kompetentaj algoritmoj por NP-plenaj problemoj rompos iujn algoritmojn de ĉifrado, ekzemple multe uzatan RSA.
#000103
Sed ĉi tiaj ŝanĝoj estas ne tiel gravoj kompare al revolucio kiun kompetenta maniero por solvado de NP-plenaj problemoj devus kaŭzi en matematiko mem.
#000104
"...ĝi devus konverti matematikon per permeso al komputilo al trovi formalan pruvon de ĉ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 ĉiujn en la jarmilaj premiaj problemoj." (Stephen Cook [7])
#000105
Matematikistoj pasigas grandan tempodaŭron penante pruvi teoremojn. Maniero kiu estas garantiita al trovi pruvojn al teoremoj, se ĝi ekzisti de "modera" amplekso, devus esence plifaciligi iuj aferojn.
#000106
Pruvo kiu montras ke P' ≠ NP ne donas praktikajn komputajn bonaĵojn malsimile al pruvo ke P = NP. Tamen ankaŭ pruvo de P ≠ NP devas prezenti grandan antaŭenigon en komputa komplikteorio kaj provizi gvidadon por estontaj esploroj. Ĝ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 solvaĵoj aŭ solvaĵoj de aliaj problemoj. Pro vasta konvinko ke P ≠ NP, multaj el ĉi tiuj movoj de fokusoj de esploro jam estas faritaj.[8]
#000107
Rezultoj pri malfacileco de la pruvo
#000108
Grandega kvanto de dediĉita esploro sen esencaj rezultoj sugestas ke la problemo estas malfacila. Fakte, iu el la plej fruktodonaj esploroj rilatantaj al ĉu P = NP estas en montrado ke ekzistantaj pruvaj teknikoj estas ne povaj sufiĉe por respondi al la demando, tial sugestante ke la novaj manieroj estas verŝajne bezonataj.
#000109
Esence ĉiuj sciataj pruvaj teknikoj en komputa komplikteorio estas de unu el la sekvaj klasifikaĵoj, kaj ĉiuj estas sciataj al esti nesufiĉaj por pruvi ke P ≠ NP:
#000110
Relativigaj pruvoj: Imagi mondon kie al ĉ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 aĵ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.[9] Pro tio ke relativigaj pruvoj povas nur pruvi frazojn kiuj estas unuforme veraj kun respekto al ĉiuj eblaj orakoloj, ĉi tio montris ke relativigaj teknikoj ne povas malkomponi demandon P = NP.
#000111
Naturaj pruvoj: En 1993, Aleksander Razborov kaj Steven Rudich difinis ĝeneralan klason de pruvaj teknikoj por cirkvitaj komplikecaj subaj baroj, nomatan kiel naturaj pruvoj. Je la tempo, ĉiuj antaŭ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 ankaŭ pruvi eĉ pli fortan frazon, kiu estas kredita al esti malvera. Tial estas malverŝajne ke naturaj pruvoj solaj povas malkomponi demandon pri P = NP.
#000112
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 ĉefa nova teknika laborilo uzata en la IP = PSPACO pruvo, kiun ili nomas kiel algebrigo, estas nesufiĉa al malkomponi demandon pri P = NP.[10]
#000113
Ĉi tiuj bariloj estas alia kaŭzo kial NP-plena problemoj estas utilaj: se polinomo-tempa algoritmo povas esti montrita por NP-plena problemo, ĉi tio devus solvi la P = NP demandon kvazaŭ tiu estas inkluzivita per la pli supraj rezultoj.
#000114
Ne estas sciata ĉ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 ĝi prenas ĝenerale.
#000115
Se kaj nur se P = NP ĉi tio estas polinomo-tempa algoritmo akceptanta NP-plenan lingvon. "Akceptanta" signifas ke ĝi donas jes-respondojn en polinoma tempo, sed estas permesita al kuri eterne kiam la respondo estas nea.
#000116
Diferenco inter solvi la problemon kaj akcepti la lingvon. estas en tio ke la solvanta algoritmo devas ĉiam halti kaj redoni jesas aŭ nean respondon. Kiel en 2008, ĝi estas nekonate ĉu ekzistas algoritmo kiu solvas la problemon en polinoma tempo. Sed se estas algoritmo kiu verŝajne faras ĉi tion en polinoma tempo, do ĉi tia algoritmo estas ricevita per anstataŭigo de la "SE" en la pli supra algoritmo per ĉi tio:
#000117
Nombregoj#Komputiloj kaj komputa komplikeco - iuj pritaksoj de tempoj de kalkulado
Listo de malfermitaj problemoj en komputiko
#000118
Oficiala priskribo de la problemo
Ian Stewart sur Minesweeper pri NP-pleneco
Gerhard J. Woeginger. La P-kontraŭ-NP paĝo. Listo de ligiloj al proponitaj solvaĵoj al la problemo. Iu el ĉi tiuj ligoj statas ke P = NP, iuj ke P ≠ NP. Verŝajna ĉi ĉiuj solvaĵoj estas malĝ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: kaŭzoj al kredi, listo de pliĝustigoj por la konvinko ke P ≠ NP
#000120