[{"text_idx": "#000001", "text": "La P kontrau\u0306 NP-problemo estas grava neklarigita problemo en komputado.\nG\u0302i demandas ke c\u0302u c\u0302iu problemo kies solvo povas esti rapide konfirmita (teknike, konfirmita en polinoma tempo) ankau\u0306 povas solvita rapide (denove, en polinoma tempo)."}, {"text_idx": "#000002", "text": "La subestaj temoj unue estis diskutitaj en la 1950-aj jaroj, en leteroj de John Forbes Nash Jr. g\u0302is la National Security Agency, kaj de Kurt Go\u0308del g\u0302is John von Neumann.\nLa preciza deklaro de la P kontrau\u0306 NP-problemo estis lanc\u0302ita 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\u0306 multaj estas la plej grava malferma problemo en la kampo.\nG\u0302i 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\u0302usta solvo."}, {"text_idx": "#000003", "text": "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\u0302o al la algoritmo (kontraste al, ekzemple, eksponenta tempo).\nLa g\u0302enerala klaso de demandoj por kiu iu algoritmo povas disponigi respondon en polinoma tempo estas nomita \"klaso P \" au\u0306 j\u0302us\" P \".\nPor 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.\nLa klaso de demandoj por kiu respondo povas esti konfirmita en polinoma tempo estas nomita NP , kiu staras por \"nedeterminisma polinoma tempo\"."}, {"text_idx": "#000005", "text": "Respondo al la P = NP- demando determinus c\u0302u problemoj kiuj povas esti konfirmitaj en polinoma tempo, kiel Sudoko, ankau\u0306 povas esti solvitaj en polinoma tempo.\nSe g\u0302i turnus tiun P =\u0338 NP, g\u0302i 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."}, {"text_idx": "#000006", "text": "Krom esti grava problemo en komputilteorio, pruvo ambau\u0306 manieroj havus profundajn implicojn por matematiko, kriptografion, algoritmesploradon, artefaritan inteligentecon, ludoteorion, multmedian pretigon, filozofion, ekonomikon kaj multaijn aliajn kampojn."}, {"text_idx": "#000008", "text": "2 Ankorau\u0306 pli pezaj problemoj\n5 Rezultoj pri malfacileco de la pruvo"}, {"text_idx": "#000009", "text": "Kvankam la P kontrau\u0306 NP- problemo estis formale difinita en 1971, ekzistis antau\u0306aj sentoj de la problemoj implikitaj, la malfacileco de pruvo, kaj la eblaj sekvoj.\nEn 1955, matematikisto John Nash skribis leteron al la NSA, kie li konjektis ke fendi sufic\u0302e kompleksan kodon postulus tempeksponenton en la longo de la s\u0302losilo.\nSe pruvite (kaj Nash estis konvene skeptika) tio implicus kion ni hodiau\u0306 nomus P =\u0338 NP, c\u0302ar proponita s\u0302losilo povas facile esti konfirmita en polinoma tempo.\nAlia mencio de la subesta problemo okazis en letero (1956) skribita fare de Kurt Go\u0308del al John von Neumann.\nGo\u0308del demandis c\u0302u teoremo-testo (nun povas ko-Np-kompleta) povus esti solvita en kvadrata au\u0306 lineara tempo, [6] kaj indikis unu el la plej gravaj sekvoj - kiu se tiel, tiam la eltrovo de matematikaj pruvoj povis esti au\u0306tomatigita."}, {"text_idx": "#000010", "text": "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\u0306fiksitan problemon.\nLa plej oftaj resursoj estas tempo (kiom multajn s\u0302tupojn g\u0302i prenas por solvi problemon) kaj spaco (kiom multe da memoro g\u0302i prenas por solvi problemon)."}, {"text_idx": "#000011", "text": "En tia analizo, modelo de la komputilo por kiu tempon devas esti analizita estas postulata.\nTipe tiaj modeloj supozas ke la komputilo estas determinisma (donita la nunan s\u0302taton de la komputilo kaj iujn ajn enigaj\u0302ojn, ekzistas nur unu ebla ago kiun la komputilo eble prenos) kaj sinsekva (g\u0302i prezentas agojn unu- post la alie)."}, {"text_idx": "#000012", "text": "El tiu teorio, la klaso P konsistas el c\u0302iuj tiuj decidoproblemoj (difinitaj malsupre) kiuj povas esti solvitaj sur determinisma sinsekva mas\u0302ino en kvanto de tempo kiu estas polinomo en la grandeco de la enigaj\u0302o;\nla klaso NP konsistas el c\u0302iuj tiuj decidoproblemoj kies pozitivaj solvoj povas esti konfirmitaj en polinoma tempo donita la dekstrajn informojn, au\u0306 ekvivalente, kies solvo povas esti trovita en polinoma tempo sur ne-determinisma mas\u0302ino.\nVers\u0302ajne la plej granda malferma demando en teoria komputiko koncernas la rilaton inter tiuj du klasoj:"}, {"text_idx": "#000013", "text": "C\u0302u P egala al NP estas?"}, {"text_idx": "#000014", "text": "En balotenketo de 100 esploristoj, (2002) 61 kredis la respondon por esti neniu, 9 kredis ke la respondo estas jes, kaj 22 estis necertaj;\n8 kredis ke la demando povas esti sendependa de la nuntempe akceptitaj aksiomoj kaj tial malpruvebla au\u0306 kontrau\u0306pruvi."}, {"text_idx": "#000015", "text": "En 2012, 10 jarojn poste, la sama balotenketo estis ripetita.\nLa 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\u0306 kontrau\u0306pruvi, 8 (5%) diris au\u0306 ne scias au\u0306 ne zorgas au\u0306 ne deziras ke la respondo estu jes nek la problemo esti solvitaj."}, {"text_idx": "#000016", "text": "Por ataki la P = NP- demandon, la koncepto de Np-tuteco estas tre utilaj.\nNp-kompletaj problemoj estas aro de problemoj al c\u0302iu el kiuj c\u0302iu alia Np-problemo povas esti reduktita en polinoma tempo, kaj kies solvo dau\u0306re povas esti konfirmita en polinoma tempo.\nTio estas, c\u0302iu NP- problemo povas esti transformita en iuj da la Np-kompletajn problemojn.\nNeformale, Np-kompleta problemo estas NP- problemo kiu estas almenau\u0306 same \"malfacila\" kiel iu alia problemo en NP."}, {"text_idx": "#000017", "text": "Np-malmolaj problemoj estas tiuj minimume same forte kiel NP- problemoj, t.e., c\u0302iuj NP- problemoj povas esti reduktitaj (en polinoma tempo) al ili.\nNp-malmolaj problemoj ne devas esti en NP, t.e., ili ne devas havi solvojn konfirmeblaj en polinoma tempo."}, {"text_idx": "#000018", "text": "Ekzemple, la bulea plenumebloproblemo estas Np-kompleta de la Kuir-Levin teoremo, tiel ke c\u0302iu kazo de iu problemo en NP povas esti transformita meh\u0302anike en kazon de la bulea plenumebloproblemo en polinoma tempo.\nLa bulea plenumebloproblemo estas unu el kvanto tiaj Np-kompletaj problemoj.\nSe entute Np-kompleta problemo estas en P, tiam g\u0302i sekvus tiun P = NP.\nTamen, multaj gravaj problemoj pruvig\u0302is esti Np-kompletaj, kaj neniu rapida algoritmo por iu da ili estas konata."}, {"text_idx": "#000019", "text": "Bazite sur la difino sole g\u0302i ne estas evidenta ke Np-kompletaj problemoj ekzistas;\ntamen, sensignifa kaj elpensita Np-kompleta problemo povas esti formulita jene: surbaze de priskribo de mas\u0302ino de Turing M garantiita por halti en polinoma tempo, faras tie ekzistu polinom-grandeca enigaj\u0302o kiun tiu M akceptos?\nG\u0302i estas en NP c\u0302ar (donita enigaj\u0302on) estas simple kontroli c\u0302u M akceptas la enigaj\u0302on simulante M;\ng\u0302i estas Np-kompleta c\u0302ar la konfirmilo por iu speciala kazo de problemo en NP povas esti c\u0302ifrita kiel polinomtempa mas\u0302ino M kiu prenas la solvon por esti konfirmita kiel enigaj\u0302o.\nTiam la demando de c\u0302u la kazo estas jes au\u0306 neniu kazo estas determinita per c\u0302u valida enigaj\u0302o ekzistas."}, {"text_idx": "#000020", "text": "La unua natura problemo pruvita por esti Np-kompleta estis la bulea plenumebloproblemo.\nKiel notite supre, tio estas la Kuir-Levin teoremo;\ng\u0302ia pruvo ke satisfiabileco estas Np-kompleta enhavas teknikajn detalojn pri mas\u0302ino de Turing kiam ili rilatigas al la difino de NP.\nTamen, post kiam tiu problemo estis pruvita por esti Np-kompleta, pruvo per redukto disponigis pli simplan manieron montri ke multaj aliaj problemoj ankau\u0306 estas Np-kompletaj, inkluzive de la subara sumproblemo diskutita pli frue.\nTiel, vasta klaso de s\u0302ajne senrilataj problemoj estas tute reduktebla unu al la alia, kaj estas en signifo \"la sama problemo\"."}, {"text_idx": "#000021", "text": "Kvankam estas nekonate c\u0302u P = NP, problemoj ekstere de P estas konataj.\nKelkaj trafaj problemoj (problemoj kiuj funkciigas ne sur normala enigaj\u0302o, sed en komputila priskribo de la enigaj\u0302o) povas esti EXPTIME-kompletaj .\nC\u0302ar povas esti montrite ke P =\u0338 ExPTIME , tiuj problemoj estas ekstere P, kaj tiel postulas pli ol polinoma tempo.\nFakte, de la tempohierarkioteoremo, ili ne povas esti solvitaj en signife malpli ol eksponenta tempo.\nEkzemploj inkludas trovi perfektan strategion por s\u0302ako (sur N \u00d7 N tabulo) [11] kaj iuj aliaj tabulludoj."}, {"text_idx": "#000022", "text": "La problemo de decidado de la vero de deklaro en Presburger-aritmetiko postulas ec\u0302 pli da tempo.\nC\u0302i tie, n estas la dau\u0306ro de la Presburger-deklaro.\nTial, la problemo povas bezoni pli ol eksponenta ruligotempo.\nEc\u0302 pli malfacilaj estas la nedecideblaj problemoj, kiel ekzemple la haltadproblemo.\nIli ne povas esti tute solvitaj per iu algoritmo, en la senco ke por iu speciala algoritmo ekzistas almenau\u0306 unu enigaj\u0302o por kiu tiu algoritmo ne produktos la g\u0302ustan respondon;\ng\u0302i au\u0306 produktos la malg\u0302ustan respondon, finig\u0302os sen donado de decida respondo, au\u0306 alie kuras eterne sen produktado de ajna respondo entute."}, {"text_idx": "#000024", "text": "G\u0302i estis montrita fare de Ladner kiun se P =\u0338 NP tiam tie ekzistu problemojn en NP kiuj estas nek en P nek Np-kompletan.\nTiaj problemoj estas nomitaj Np-mezaj problemoj.\nLa grafea izomorfioproblemo, la diskretlogaritma problemo kaj la faktorigo de entjerproblemo estas ekzemploj de problemoj kreditaj esti Np-mezaj.\nIli estas kelkaj el la tre malmultaj NP- problemoj ne konataj esti en P au\u0306 esti Np-kompletaj."}, {"text_idx": "#000025", "text": "La grafea izomorfioproblemo estas la komputila problemo de determinado c\u0302u du finhavaj grafeoj estas izomorfaj.\nGrava neklarigita problemo en kompleksecteorio estas c\u0302u la grafea izomorfioproblemo estas en P, Np-kompleta, au\u0306 Np-meza.\nLa respondo ne estas konata, sed estas kredite ke la problemo estas almenau\u0306 ne Np-kompleta.\nSe grafeizomorfio estas Np-kompleta, la polinomtempa hierarkio kolapsas al g\u0302ia dua nivela.\nC\u0302ar estas g\u0302enerale kredite ke la polinomhierarkio ne kolapsas al iu finhava nivelo, estas kredite ke grafeizomorfio ne estas Np-kompleta.\nLa plej bona algoritmo por tiu problemo, pro La\u0301szlo\u0301 Babai kaj Eugene Luks, havas ruligotempon 2O (\u221a nlog ( n) por grafeoj kun n verdglacioj."}, {"text_idx": "#000026", "text": "La faktorigo de entjerproblemo estas la komputila problemo da determinado de la c\u0302efa faktorigado de antau\u0306fiksita entjero.\nVortumita kiel decidoproblemo, g\u0302i estas la problemo de decidado c\u0302u la enigaj\u0302o havas faktoron malpli ol k.\nNeniu efika faktorigo de entjeralgoritmo estas konata, kaj tiu fakto formas la bazon de pluraj modernaj kriptigaj sistemoj, kiel ekzemple la RSA algoritmo.\nLa faktorigo de entjerproblemo estas en NP kaj en ko-Np (kaj ec\u0302 en SUPRE kaj ko-UP [16] ).\nSe la problemo estas Np-kompleta, la polinomtempa hierarkio kolapsos al g\u0302ia unua nivelo (t.e., NP = ko-Np).\nLa plej konata algoritmo por faktorigo de entjero estas la g\u0302enerala numero-kampokribrilo, kiu prenas atendatan tempon"}, {"text_idx": "#000027", "text": "Tamen, la plej konata kvantumalgoritmo por tiu problemo, la algoritmo de Shor, enrutinigas polinoman tempon, kvankam tio ne indikas kie la problemo kus\u0302as kun respekto al ne-kvantaj kompleksecklasoj."}, {"text_idx": "#000028", "text": "C\u0302io el c\u0302i-supra diskuto supozis ke P signifas \"facila\" kaj \"ne en P \" signifas \"forte\", supozon konatan kiel la disertaj\u0302o de Cobham .\nG\u0302i estas ofta kaj sufic\u0302e preciza supozo en kompleksecteorio;\ntamen, g\u0302i havas kelkajn avertrimarkojn."}, {"text_idx": "#000029", "text": "Unue, g\u0302i ne estas c\u0302iam vera en praktiko.\nTeoria polinomalgoritmo povas havi ekstreme grandajn konstantajn faktorojn au\u0306 eksponentojn tiel igante g\u0302in nepraktika.\nAliflanke, ec\u0302 se problemo pruvig\u0302as esti Np-kompleta, kaj ec\u0302 se P =\u0338 NP, povas dau\u0306re ekzisti efikaj aliroj al pritraktado de la problemo en praktiko.\nEkzistas algoritmoj por multaj Np-kompletaj problemoj, kiel ekzemple la tornistroproblemo, la vojag\u0302antvendista problemo kaj la bulea plenumebloproblemo, kiuj povas solvi al optimeco multajn real-mondajn kazojn en akceptebla tempo.\nLa empiria mezum-kaza komplekseco (tempo vs. problemgrandeco) de tiaj algoritmoj povas esti surprize malalta.\nEkzemplo estas la simpla algoritmo en linia programado, kiu laboras surprize bone en praktiko;\nmalgrau\u0306 havado de eksponenta plej malbonkaza polinoma tempo g\u0302i kuras sur alparo kun la plej konataj polinomtempaj algoritmoj."}, {"text_idx": "#000030", "text": "Due, ekzistas specoj de komputadoj kiuj ne harmonias kun la mas\u0302ino de Turing-modelo sur kiu P kaj NP estas difinitaj, kiel ekzemple kvantekomputado kaj hazardigitaj algoritmoj."}, {"text_idx": "#000031", "text": "Lau\u0306 balotenketoj, [8] [19] la plej multaj komputikistoj kredas tiun P =\u0338 NP.\nEsenca 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).\nTiuj algoritmoj estis serc\u0302itaj long antau\u0306 ol la koncepto de Np-tuteco estis ec\u0302 difinita ( la 21 Np-kompletaj problemoj de Karp, inter la unua trovitaj, estis c\u0302iuj bonkonataj ekzistantaj problemoj tiutempe kiam ili pruvig\u0302is esti Np-kompletaj).\nKrome, la rezulto P = NP implicus multaijn aliajn surprizajn rezultojn kiuj vers\u0302ajne nuntempe estas falsaj, kiel ekzemple NP = ko-Np kaj P = PH ."}, {"text_idx": "#000032", "text": "Estas ankau\u0306 intuicie argumentite ke la ekzisto de problemoj kiuj estas malmolaj solvi krom por kiujn la solvoj facile konfirmeblas matc\u0302oj real-mondan sperton."}, {"text_idx": "#000034", "text": "Aliflanke, kelkaj esploristoj kredas ke ekzistas superoptimismo en kredado de P =\u0338 NP kaj ke esploristoj devus esplori pruvojn de P = NP ankau\u0306.\nEkzemple, en 2002 tiuj deklaroj estis faritaj: [8]"}, {"text_idx": "#000035", "text": "La c\u0302efargumento en favoro de P =\u0338 NP estas la totala manko de fundamenta progreso en la areo de g\u0302isfunda serc\u0302o.\nTio estas, en mia opinio, tre malforta argumento.\nLa spaco de algoritmoj estas tre granda kaj ni estas nur komence de g\u0302ia esplorado.\nLa rezolucio de la lasta teoremo de Fermat ankau\u0306 montras ke tre facilaj demandoj povas esti solvitaj nur per tre profundaj teorioj."}, {"text_idx": "#000036", "text": "Esti alkroc\u0302ita al konjekto ne estas bona gvidisto priesplori planadon.\nOni c\u0302iam devus provi ambau\u0306 indikojn de c\u0302iu problemo.\nAntau\u0306jug\u0302o igis famajn matematikistojn malsukcesi solvi famajn problemojn kies solvo estis kontrau\u0306a al iliaj atendoj, ec\u0302 se ili evoluigis c\u0302iujn metodojn postulatajn."}, {"text_idx": "#000037", "text": "Unu el la kialoj kiujn la problemo altiras tiel al multe da atento estas la sekvoj de la respondo.\nAmbau\u0306 indikoj de rezolucio avancus teorion grandege, kaj eble havus enormajn praktikajn sekvojn ankau\u0306."}, {"text_idx": "#000038", "text": "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.\nEstas ankau\u0306 eble ke pruvo ne kondukus rekte al efikaj metodoj, eble se la pruvo estas ne-helpema, au\u0306 la grandeco de la salta polinomo estas tro granda por esti efika en praktiko.\nLa sekvoj, kaj pozitivaj kaj negativaj, ekestas c\u0302ar diversaj Np-kompletaj problemoj estas fundamentaj en multaj kampoj."}, {"text_idx": "#000039", "text": "Kriptografio, ekzemple, dependas de certaj problemoj estantaj malfacila.\nHelpema kaj efika solvo [Noto 2] al Np-kompleta problemo kiel ekzemple 3-SAT rompus la plej multajn ekzistantajn kriptsistemojn inkluzive de:"}, {"text_idx": "#000040", "text": "publiks\u0302losila kriptografio, [21] fundamento por multaj modernaj sekurecaplikoj kiel ekzemple sekuraj financaj transakcioj super la Interreto;\nsimetriaj c\u0302ifroj kiel ekzemple AES au\u0306 3DES, [22] uzitaj por la c\u0302ifrado de komunikaddatenoj.\nunudirektaj funkcioj uzite en kriptiga hakado.\nLa problemon de trovado de antau\u0306-bildo kiu hakas al antau\u0306fiksita valoro [23] devas malfacili esti utila, kaj ideale devus postuli eksponentan tempon.\nTamen, c\u0302u P NP, tiam trovanta antau\u0306-bildon M povas esti finita polinoman tempon, tra redukto al SAT."}, {"text_idx": "#000041", "text": "Tiuj devus esti modifitaj au\u0306 anstatau\u0306igita per informo-teorie sekuraj solvoj ne esence bazite sur P-NP-ekvivalenteco."}, {"text_idx": "#000042", "text": "Aliflanke, ekzistas grandegaj pozitivaj sekvoj kiuj sekvus el igado de akordig\u0302ema multaj nuntempe matematike nesolveblaj problemoj.\nEkzemple, multaj problemoj en operacianalizo estas Np-kompletaj, kiel ekzemple kelkaj specoj de entjerprogramado kaj la migranta vendistoproblemo.\nEfikaj solvoj al tiuj problemoj havus grandegajn implicojn por log\u0302istiko.\nMultaj aliaj gravaj problemoj, kiel ekzemple kelkaj problemoj en proteinstrukturprognozo, ankau\u0306 estas Np-kompletaj;\nse tiuj problemoj estis efike solveblaj g\u0302i povus sproni konsiderindajn progresojn en vivsciencoj kaj bioteknologio."}, {"text_idx": "#000043", "text": "Sed tiaj s\u0302ang\u0302oj povas palig\u0302i en signifo komparite kun la revolucio efika metodo por solvado de Np-kompletaj problemoj kau\u0306zus en matematiko mem.\nGo\u0308del, en liaj fruaj pensoj sur komputadokomplekseco, notis ke mekanika metodo kiu povis solvi ajnan problemon revoluciigus matematikon: [26]"}, {"text_idx": "#000044", "text": "Se vere ekzistus mas\u0302ino kun \u03c6 (n) \u223c k \u22c5 n (au\u0306 ec\u0302 \u223c k \u22c5 N kun nombro), tio havus sekvojn de la plej granda graveco.\nNome, g\u0302i evidente signifus tion malgrau\u0306 la undecidabileco de la Entscheidungsproblem, la mensa laboro de matematikisto koncerne Jes-au\u0306-neniujn demandojn povus esti tute anstatau\u0306igita per mas\u0302ino.\nPost c\u0302io, oni simple devus elekti la naturan pli sensentan n tiel grandan ke kiam la mas\u0302ino ne faras rezulton, sonas neniun racie por pensi pli pri la problemo."}, {"text_idx": "#000046", "text": "g\u0302i transformus matematikon permesante al komputilo trovi formalan pruvon de iu teoremo kiu havas pruvon de akceptebla longo, c\u0302ar formalaj pruvoj povas facile esti rekonitaj en polinoma tempo.\nEkzemploproblemoj povas bone inkludi c\u0302iujn la CMI-premioproblemoj."}, {"text_idx": "#000047", "text": "Esplormatematikistoj pasigas siajn karierojn provante pruvi teoremoj, kaj kelkaj pruvoj prenis jardekojn au\u0306 ec\u0302 jarcentojn por trovi post kiam problemoj estis deklaritaj - ekzemple, la lasta teoremo de Fermat dau\u0306ris pli ol tri jarcentojn por pruvi.\nMetodo kiu estas garantiita por trovi pruvojn al teoremoj, oni devus ekzisti de \"akceptebla\" grandeco, esence finus tiun lukton."}, {"text_idx": "#000048", "text": "Donald Knuth deklaris ke li kredis ke P = NP, sed estas rezervita koncerne la efikon de ebla pruvo: [29]"}, {"text_idx": "#000049", "text": "mi ne kredas ke la egaleco P = NP montrig\u0302os por helpema ec\u0302 se g\u0302i estas pruvita, c\u0302ar tia pruvo preskau\u0306 certe estos nonkonstruktive."}, {"text_idx": "#000050", "text": "Pruvo ke montrita ke P =\u0338 NP malhavus la praktikajn komputilajn avantag\u0302ojn de pruvo tiu P = NP, sed tamen reprezentus tre signifan antau\u0306enig\u0302on en komputa komplikeco kaj disponigus konsiladon por estonta esplorado.\nG\u0302i permesus unun por montri lau\u0306 formala maniero ke multaj komunaj problemoj ne povas esti solvitaj efike, tiel ke la atento de esploristoj povas esti temigis partajn solvojn au\u0306 solvojn al aliaj problemoj.\nPro g\u0302eneraligita kredo je P =\u0338 NP, multe de tiu enfokusigo de esplorado jam okazis."}, {"text_idx": "#000052", "text": "Rezultoj pri malfacileco de pruvo"}, {"text_idx": "#000053", "text": "Kvankam la P = NP- problemo mem restas malfermaj malgrau\u0306 milion-dolara premio kaj enorma kvanto de diligenta esplorado, laboroj por solvi la problemon kondukis al pluraj novaj teknikoj.\nAparte, iuj el la plej fruktodona esplorado ligita al la P = NP- problemo estis en montrado ke ekzistantaj pruvteknikoj ne estas sufic\u0302e potencaj por respondi la demandon, tiel sugestante ke romano teknikaj aliroj estu postulataj."}, {"text_idx": "#000054", "text": "Kiel kroma indico por la malfacileco de la problemo, esence c\u0302iuj konataj pruvteknikoj en komputkomplikeca au\u0306tuno en unu el la post klasifikoj, c\u0302iu el kiu povas esti nesufic\u0302a pruvi tiun P =\u0338 NP:"}, {"text_idx": "#000055", "text": "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\u0306 maniero ne ekskludite per c\u0302i-supraj rezultoj."}, {"text_idx": "#000056", "text": "Tiuj barieroj ankau\u0306 igis kelkajn komputikistojn sugesti ke la P kontrau\u0306 NP- problemo povas esti sendependa de normaj aksiomsistemoj kiel ZFC (ne povas esti pruvita au\u0306 kontrau\u0306pruvita ene de ili).\nLa interpreto de sendependecrezulto povis esti tiel au\u0306 neniu polinomtempa algoritmo ekzistas por iu Np-kompleta problemo, kaj tia pruvo ne povas esti konstruita en (ekz.) ZFC, au\u0306 ke polinomtempaj algoritmoj por Np-kompletaj problemoj povas ekzisti, sed estas maleble pruvi en ZFC ke tiaj algoritmoj estas g\u0302ustaj.\nTamen, se g\u0302i povas esti montrita, uzante teknikojn de la speco kiuj povas nuntempe esti uzeblaj, ke la problemo ne povas esti decidita ec\u0302 kun multe pli malfortaj supozoj etendantaj la Peano-aksiomojn (Patro) por entjeraritmetiko, tiam tie nepre ekzistus preskau\u0306-polinomatempaj algoritmoj por c\u0302iu problemo en NP.\nTial, se oni kredas (c\u0302ar plej multe de la komplekseco teoriuloj faras) ke ne c\u0302iuj problemoj en NP havas efikajn algoritmojn, g\u0302i sekvus tiujn pruvojn de sendependeco uzanta tiujn teknikojn ne povas esti ebla.\nPlie, tiu rezulto implicas tion pruvantan sendependeco de Patro au\u0306 ZFC uzanta nuntempe konatajn teknikojn estas al neniu pli facila ol pruvado de la ekzisto de efikaj algoritmoj por c\u0302iuj problemoj en NP."}, {"text_idx": "#000058", "text": "La P = kiun NP- problemo povas esti reproponita lau\u0306 esprimebla certaj klasoj de logikaj deklaroj, kiel rezulto de laboro en priskriba komplekseco."}, {"text_idx": "#000059", "text": "Pripensu c\u0302iujn lingvojn de finhavaj strukturoj kun fiksa signaturo inkluzive de linia ord rilato.\nTiam, tute tiaj lingvoj en P povas esti esprimitaj en unuaorda logiko kun la aldono de tau\u0306ga malplej fikspunkto-kombinator.\nEfike, tio, en kombinaj\u0302o kun la ordo, permesas la difinon de rekursivaj funkcioj.\nTiel longe kiel la signaturo enhavas almenau\u0306 unu predikaton au\u0306 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\u0302uste karakterizas P."}, {"text_idx": "#000060", "text": "Simile, NP estas la aro de lingvoj esprimeblaj en ekzisteca duaorda logiko - t.e., duaorda logiko malvastanima ekskludi c\u0302iu-kvantoron super rilatoj, funkcioj, kaj subaroj.\nLa lingvoj en la polinomhierarkio, PH , egalrilatas al c\u0302io el duaorda logiko.\nTiel, 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?\nLa vorto \"ekzisteca\" ec\u0302 povas esti finita de la antau\u0306a 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)."}, {"text_idx": "#000061", "text": "Neniu algoritmo por iu Np-kompleta problemo povas kuri en polinoma tempo.\nTamen, ekzistas algoritmoj konataj pro Np-kompletaj problemoj kun la posedaj\u0302o kiun se P = NP, tiam la algoritmo prizorgas en polinoma tempo dum akceptado de kazoj (kvankam kun grandegaj konstantoj, igante la algoritmon nepraktika).\nTamen, tiuj algoritmoj ne kvalifikig\u0302as kiel polinoma tempo c\u0302ar ilia veturtempo sur malaprobado kazoj ne estas polinomoj.\nLa sekva algoritmo, pro Levin (sen iu citaj\u0302o), estas tia ekzemplo malsupre.\nG\u0302i funkcias en polinoma tempo per enigaj\u0302oj kiuj estas en SUBARO-SUMO se kaj nur se P = NP:"}, {"text_idx": "#000062", "text": "Se, kaj nur se, P = NP, tiam tio estas polinomtempa algoritmo akceptanta Np-kompletan lingvon.\n\"Akceptante\" rimedoj g\u0302i donas \"jes\" respondojn en polinoma tempo, sed estas permesitaj kuri eterne kiam la respondo \"ne\" estas (ankau\u0306 konata kiel semi-algoritmo)."}, {"text_idx": "#000063", "text": "Tiu algoritmo estas grandege nepraktika, ec\u0302 se P = NP.\nSe la plej mallonga programo kiu povas solvi SUBARO-SUMON en polinoma tempo estas b pecojn longa, c\u0302i-supra algoritmo provos almenau\u0306 2 b \u22121 aliaj programoj unue."}, {"text_idx": "#000064", "text": "Koncipe parolante, decidoproblemo estas problemo kiu prenas kiel enigaj\u0302o iun s\u0302nuron w super alfabeto \u03c3, kaj produktaj\u0302ojn \"jes\" au\u0306 \"ne\".\nSe ekzistas algoritmo (diru mas\u0302inon de Turing, au\u0306 komputilan programon kun nelimigita memoro) kiu povas produkti la g\u0302ustan respondon por iu enigo-literaj\u0302o de longo n en maksimume cnk s\u0302tupoj, kie k kaj c estas konstantoj sendependaj de la enigo-literaj\u0302o, tiam ni diras ke la problemo povas esti solvita en polinoma tempo kaj ke ni metas g\u0302in en la klason P.\nFormale, P estas difinita kiel la aro de c\u0302iuj lingvoj kiuj povas esti deciditaj per determinisma polinomtempa mas\u0302ino de Turing."}, {"text_idx": "#000065", "text": "kaj determinisma polinomtempa mas\u0302ino de Turing estas determinisma mas\u0302ino de Turing M kiu kontentigas la sekvajn du kondic\u0302ojn:"}, {"text_idx": "#000066", "text": "M haltoj sur c\u0302io enir w kaj"}, {"text_idx": "#000067", "text": "NP povas esti difinita simile uzante nedeterminismajn mas\u0302inon de Turing (la tradiciajn maniero).\nTamen, moderna aliro al difini NP devas utiligi la koncepton de atestilo kaj konfirmilo.\nFormale, 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."}, {"text_idx": "#000068", "text": "Lasu L esti lingvo super finhava alfabeto, \u03c3."}, {"text_idx": "#000069", "text": "Mas\u0302ino de Turing kiu decidas Lr estas nomitaj konfirmilo por L kaj y tia ke ( x, y\nR estas nomita atestilo pri membreco de x en L."}, {"text_idx": "#000070", "text": "G\u0302enerale, konfirmilo ne devas esti polinomtempa.\nTamen, por L por esti en NP, devas ekzisti konfirmilo kiu kuras en polinoma tempo."}, {"text_idx": "#000071", "text": "Klare, la demando de c\u0302u fakto x estas kunmetaj\u0302o estas ekvivalenta al la demando de c\u0302u x estas membro de KUNMETAJ\u0302O.\nPovas esti montrite ke SINTEXA \u2208 NP de konfirmado ke g\u0302i kontentigas c\u0302i-supran difinon (se ni identigas naturajn nombrojn kun iliaj binaraj reprezentantaroj)."}, {"text_idx": "#000072", "text": "Ekzistas multaj ekvivalentaj manieroj priskribi Np-tuteco."}, {"text_idx": "#000074", "text": "L estas Np-kompleta se, kaj nur se, la sekvaj du kondic\u0302oj estas kontentigitaj:"}, {"text_idx": "#000076", "text": "Alternative, se L \u2208 NP, kaj ekzistas alia Np-kompleta problemo kiu povas esti polinomtempa reduktita al L, tiam L estas Np-kompleta.\nTio estas ofta maniero pruvi iu nova problemo estas Np-kompleta."}, {"text_idx": "#000077", "text": "Listo de nesolvitaj problemoj en matematiko"}, {"text_idx": "#000078", "text": "^ A nondeterministic mas\u0302ino de Turing can move to a state that is not determined by the previous state.\nSuch a machine could solve a Np problem in polinoma tempo by falling into the correct answer state (by luck), then conventionally verifying it.\nSuch machines are not practical for solving realistic problems but can be used as theoretical models.\n^ Ekzakte kiel efika solvo devas devi prezenti minacon al kriptografio dependas de la detaloj."}, {"text_idx": "#000082", "text": "La interrilato inter la rultempaj komplikecaj klasoj P kaj NP estas nesolvita demando en komputa komplikteorio."}, {"text_idx": "#000083", "text": "En esenco la demando c\u0302u P = NP estas jena: se jes-respondo al decida problemo povas esti kontrolita en polinoma tempo, c\u0302u la respondo povas ankau\u0306 esti komputita en polinoma tempo?"}, {"text_idx": "#000084", "text": "Decida problemo estas problemo kun respondo jes au\u0306 ne. Solvado estas en polinoma tempo se g\u0302i estas farata en maksimume c\u00b7nk pas\u0302oj, kie n estas longo de la enigo kaj k kaj c estas konstantoj sendependaj de la enigo."}, {"text_idx": "#000085", "text": "La demando c\u0302u P = NP demando devas difini c\u0302u problemoj similaj al la subara suma problemo estas facile (en polinoma tempo) komputeblaj. Se P =\u0338 NP, do iuj NP problemoj estas signife \"pli pezaj\" por komputi ol por kontroli."}, {"text_idx": "#000086", "text": "La limigo al jes/ne problemoj estas negrava; la rezultanta problemo kun pli komplika respondo estas permesata, la demando c\u0302u FP = FNP estas ekvivalenta al c\u0302u P = NP.[1]"}, {"text_idx": "#000087", "text": "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\u0302oj plej vers\u0302ajne 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\u0302iu problemo en NP povas reduktig\u0302i en polinoma tempo. Ekzemple, la decida problema versio de la problemo pri vojag\u0302anta komizo estas NP-plena, tiel c\u0302iu apero de c\u0302iu problemo en NP povas esti konvertita mekanike en aperon de la problemo pri vojag\u0302a komizo, en polinoma tempo. La problemo pri vojag\u0302anta komizo estas unu el multaj c\u0302i 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."}, {"text_idx": "#000088", "text": "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\u0302ino de Turing M kiu estas garantiita al halti en polinoma tempo, c\u0302u ekzistas polinomo-ampleksa enigo kiun M akceptas (redonas rezulton jes)?[2] G\u0302i estas en NP c\u0302ar, por donita enigo, estas simple kontroli c\u0302u M akceptas la enigon per simulado de M. G\u0302i estas NP-peza c\u0302ar la kontrolilo por c\u0302iu aparta apero de problemo en NP povas esti kodita kiel polinomo-tempa mas\u0302ino M kiu prenas la kontrolatan solvaj\u0302on kiel enigo."}, {"text_idx": "#000089", "text": "La unua natura problemo pruvita al esti NP-plena estis la bulea plenumebloproblemo. C\u0302i tiu rezulto estas sciata kiel teoremo de Cook\u2013Levin. G\u0302ia pruvo ke la bulea plenumebloproblemo estas NP-plena enhavas teknikajn detalojn pri mas\u0302inoj de Turing kiel ili rilatas al la difino de NP. Tamen, post kiam c\u0302i tiu problemo estis pruvita al esti NP-plena, pruvo per malpligrandig\u0302o provizas pli simplan manieron montradi ke multaj aliaj problemoj estas en c\u0302i tiu klaso. Tial, vasta klaso de kvazau\u0306 neinterrilatantaj problemoj estas c\u0302iuj redukteblaj unu la alian, kaj estas tiel en senso la sama problemo."}, {"text_idx": "#000090", "text": "Kvankam estas nekonate c\u0302u 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\u0302ar g\u0302i povas esti montrite ke P EKSPTEMPO, c\u0302i 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."}, {"text_idx": "#000091", "text": "La problemo de kontrolado vereco de frazo en aritmetiko de Presburger postulas ec\u0302 pli grandan tempon. Fischer kaj Michael O. Rabin pruvis en 1974 ke c\u0302iu 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\u0302i tie, la problemo estas sciata al bezoni pli ol eksponentan tempon. Ec\u0302 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\u0302iu aparta algoritmo estas minimume unu enigo por kiu la algoritmo ne produktas la g\u0302ustan respondon; g\u0302i produktas la eraran respondon au\u0306 rulig\u0302as eterne sen produktado de respondo."}, {"text_idx": "#000093", "text": "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]"}, {"text_idx": "#000094", "text": "En 2002 estas farita pridemandado de opinio pri c\u0302u 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\u0306 malpruvi g\u0302in.[5]"}, {"text_idx": "#000095", "text": "Plejparo de komputilaj sciencistoj kredas ke P =\u0338 NP. S\u0302losila kau\u0306zo por c\u0302i tiu konvinko estas ke post jardekoj da studado de la afero, ne estas trovita polinomo-tempa algoritmo por iu NP-peza problemo. C\u0302i tiuj algoritmoj estis serc\u0302itaj longe antau\u0306 kiam la koncepto de NP-pleneco estis inventita. C\u0302iuj 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."}, {"text_idx": "#000096", "text": "Estas ankau\u0306 intuicie argumentite ke la ekzisto de problemoj kiuj estas pezaj al solvi sed por kiuj la solvaj\u0302oj estas facilaj al kontroli koincidas kun reala monda sperto."}, {"text_idx": "#000097", "text": "Aliflanke, iuj esploristoj kredas ke oni tro kredas al P =\u0338 NP kaj devus esplori ankau\u0306 pruvojn de P = NP. Ekzemple, en 2002 c\u0302i tiuj propozicioj estis faritaj:[5]"}, {"text_idx": "#000098", "text": "\"La c\u0302efa argumento en favoro de P =\u0338 NP estas la tuteca manko de fundamenta progreso en la areo de elc\u0302erpa serc\u0302o. C\u0302i tio estas, miaopinie, tre malforta argumento. La spaco de algoritmoj estas tre granda kaj oni estas nur je la komenco de g\u0302ia esplorado. [. . .] La solvado de lasta teoremo de Fermat ankau\u0306 montras ke tre simplaj demandoj povas esti responditaj nur per tre profundaj teorioj.\" (Moshe Y. Vardi, Universitato Rice)\n\"Alfiksado de spekulativo estas ne bona gvido al planado de esploro. Oni devus c\u0302iam provi ambau\u0306 direktojn de c\u0302iu problemo. Antau\u0306jug\u0302o kau\u0306zis famajn matematikistojn al malsukcesi en solvado de famaj problemoj kies solvaj\u0302o estis kontrau\u0306a al iliaj ekspektoj, ec\u0302 kvankam ili ellaboris c\u0302iujn bezonatajn manierojn.\" (Anil Nerode, Universitato Cornell)"}, {"text_idx": "#000099", "text": "\"La c\u0302efa argumento en favoro de P =\u0338 NP estas la tuteca manko de fundamenta progreso en la areo de elc\u0302erpa serc\u0302o. C\u0302i tio estas, miaopinie, tre malforta argumento. La spaco de algoritmoj estas tre granda kaj oni estas nur je la komenco de g\u0302ia esplorado. [. . .] La solvado de lasta teoremo de Fermat ankau\u0306 montras ke tre simplaj demandoj povas esti responditaj nur per tre profundaj teorioj.\" (Moshe Y. Vardi, Universitato Rice)"}, {"text_idx": "#000100", "text": "\"Alfiksado de spekulativo estas ne bona gvido al planado de esploro. Oni devus c\u0302iam provi ambau\u0306 direktojn de c\u0302iu problemo. Antau\u0306jug\u0302o kau\u0306zis famajn matematikistojn al malsukcesi en solvado de famaj problemoj kies solvaj\u0302o estis kontrau\u0306a al iliaj ekspektoj, ec\u0302 kvankam ili ellaboris c\u0302iujn bezonatajn manierojn.\" (Anil Nerode, Universitato Cornell)"}, {"text_idx": "#000101", "text": "Unu el la kau\u0306zoj kial la problemo allogas tiom da atento estas la konsekvencoj de la respondo."}, {"text_idx": "#000102", "text": "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\u0306staremaj problemoj. Ekzemple, multaj problemoj en operaciesploro estas NP-plenaj, ekzemple iuj specoj de entjera programado, kaj la vojag\u0302anta komiza problemo. Kompetentaj solvaj\u0302oj al c\u0302i tiuj problemoj devus havi enormajn implikaciojn por log\u0302istiko. Multaj aliaj gravaj problemoj, ekzemple iuj problemoj en proteina struktura antau\u0306diro estas ankau\u0306 NP-plenaj;[6]. Se c\u0302i tiuj problemoj estis solveblaj kompetente rezultig\u0302as konsiderebla antau\u0306enigo en biologio."}, {"text_idx": "#000103", "text": "De la alia flanko trovo de kompetentaj algoritmoj por NP-plenaj problemoj rompos iujn algoritmojn de c\u0302ifrado, ekzemple multe uzatan RSA."}, {"text_idx": "#000104", "text": "Sed c\u0302i tiaj s\u0302ang\u0302oj estas ne tiel gravoj kompare al revolucio kiun kompetenta maniero por solvado de NP-plenaj problemoj devus kau\u0306zi en matematiko mem."}, {"text_idx": "#000105", "text": "\"...g\u0302i devus konverti matematikon per permeso al komputilo al trovi formalan pruvon de c\u0302iu 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\u0302iujn en la jarmilaj premiaj problemoj.\" (Stephen Cook [7])"}, {"text_idx": "#000106", "text": "Matematikistoj pasigas grandan tempodau\u0306ron penante pruvi teoremojn. Maniero kiu estas garantiita al trovi pruvojn al teoremoj, se g\u0302i ekzisti de \"modera\" amplekso, devus esence plifaciligi iuj aferojn."}, {"text_idx": "#000107", "text": "Pruvo kiu montras ke P' =\u0338 NP ne donas praktikajn komputajn bonaj\u0302ojn malsimile al pruvo ke P = NP. Tamen ankau\u0306 pruvo de P =\u0338 NP devas prezenti grandan antau\u0306enigon en komputa komplikteorio kaj provizi gvidadon por estontaj esploroj. G\u0302i 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\u0302oj au\u0306 solvaj\u0302oj de aliaj problemoj. Pro vasta konvinko ke P =\u0338 NP, multaj el c\u0302i tiuj movoj de fokusoj de esploro jam estas faritaj.[8]"}, {"text_idx": "#000108", "text": "Rezultoj pri malfacileco de la pruvo"}, {"text_idx": "#000109", "text": "Grandega kvanto de dedic\u0302ita esploro sen esencaj rezultoj sugestas ke la problemo estas malfacila. Fakte, iu el la plej fruktodonaj esploroj rilatantaj al c\u0302u P = NP estas en montrado ke ekzistantaj pruvaj teknikoj estas ne povaj sufic\u0302e por respondi al la demando, tial sugestante ke la novaj manieroj estas vers\u0302ajne bezonataj."}, {"text_idx": "#000110", "text": "Esence c\u0302iuj sciataj pruvaj teknikoj en komputa komplikteorio estas de unu el la sekvaj klasifikaj\u0302oj, kaj c\u0302iuj estas sciataj al esti nesufic\u0302aj por pruvi ke P =\u0338 NP:"}, {"text_idx": "#000111", "text": "Relativigaj pruvoj: Imagi mondon kie al c\u0302iu 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\u0302oj, 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 =\u0338 NP por aliaj orakoloj.[9] Pro tio ke relativigaj pruvoj povas nur pruvi frazojn kiuj estas unuforme veraj kun respekto al c\u0302iuj eblaj orakoloj, c\u0302i tio montris ke relativigaj teknikoj ne povas malkomponi demandon P = NP."}, {"text_idx": "#000112", "text": "Naturaj pruvoj: En 1993, Aleksander Razborov kaj Steven Rudich difinis g\u0302eneralan klason de pruvaj teknikoj por cirkvitaj komplikecaj subaj baroj, nomatan kiel naturaj pruvoj. Je la tempo, c\u0302iuj antau\u0306e 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 =\u0338 NP uzante naturan pruvon, oni bezone devas ankau\u0306 pruvi ec\u0302 pli fortan frazon, kiu estas kredita al esti malvera. Tial estas malvers\u0302ajne ke naturaj pruvoj solaj povas malkomponi demandon pri P = NP."}, {"text_idx": "#000113", "text": "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\u0302efa nova teknika laborilo uzata en la IP = PSPACO pruvo, kiun ili nomas kiel algebrigo, estas nesufic\u0302a al malkomponi demandon pri P = NP.[10]"}, {"text_idx": "#000114", "text": "C\u0302i tiuj bariloj estas alia kau\u0306zo kial NP-plena problemoj estas utilaj: se polinomo-tempa algoritmo povas esti montrita por NP-plena problemo, c\u0302i tio devus solvi la P = NP demandon kvazau\u0306 tiu estas inkluzivita per la pli supraj rezultoj."}, {"text_idx": "#000115", "text": "Ne estas sciata c\u0302u 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\u0302i prenas g\u0302enerale."}, {"text_idx": "#000116", "text": "Se kaj nur se P = NP c\u0302i tio estas polinomo-tempa algoritmo akceptanta NP-plenan lingvon. \"Akceptanta\" signifas ke g\u0302i donas jes-respondojn en polinoma tempo, sed estas permesita al kuri eterne kiam la respondo estas nea."}, {"text_idx": "#000117", "text": "Diferenco inter solvi la problemon kaj akcepti la lingvon. estas en tio ke la solvanta algoritmo devas c\u0302iam halti kaj redoni jesas au\u0306 nean respondon. Kiel en 2008, g\u0302i estas nekonate c\u0302u ekzistas algoritmo kiu solvas la problemon en polinoma tempo. Sed se estas algoritmo kiu vers\u0302ajne faras c\u0302i tion en polinoma tempo, do c\u0302i tia algoritmo estas ricevita per anstatau\u0306igo de la \"SE\" en la pli supra algoritmo per c\u0302i tio:"}, {"text_idx": "#000118", "text": "Nombregoj#Komputiloj kaj komputa komplikeco - iuj pritaksoj de tempoj de kalkulado\nListo de malfermitaj problemoj en komputiko"}, {"text_idx": "#000120", "text": "Oficiala priskribo de la problemo\nIan Stewart sur Minesweeper pri NP-pleneco\nGerhard J. Woeginger. La P-kontrau\u0306-NP pag\u0302o. Listo de ligiloj al proponitaj solvaj\u0302oj al la problemo. Iu el c\u0302i tiuj ligoj statas ke P = NP, iuj ke P =\u0338 NP. Vers\u0302ajna c\u0302i c\u0302iuj solvaj\u0302oj estas malg\u0302ustaj.\nKomputa komplikeco de ludoj kaj enigmoj\nKomplikeca zoo de Scott Aaronson P, NP\nQeden, vikio kiu celas al solvi la jarmilaj premiaj problemoj (\"suben por konservado\" kiel de 15-a de Julio de 2008)\nBlogo de Scott Aaronson: kau\u0306zoj al kredi, listo de plig\u0302ustigoj por la konvinko ke P =\u0338 NP"}]