{"id":2310,"date":"2010-08-09T23:12:49","date_gmt":"2010-08-09T21:12:49","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2310"},"modified":"2022-10-10T17:41:27","modified_gmt":"2022-10-10T15:41:27","slug":"p-np-o-no","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2010\/08\/09\/p-np-o-no\/","title":{"rendered":"P != NP  (o no?)"},"content":{"rendered":"<p>Oggi la comunit\u00e0 matematica mondiale \u00e8 stata scossa da una notizia bomba: un ricercatore dell&#8217;HP, Vinoy Deolalikar, ha affermato di avere dimostrato che effettivamente P != NP. Su <a href=\"http:\/\/scientopia.org\/blogs\/goodmath\/2010\/08\/09\/holy-freaking-cow-p-np\/\">Good Math, Bad Math<\/a>, MarkCC fa un rapido resoconto del problema per i matematici non esperti in teoria della complessit\u00e0. E per chi matematico non \u00e8?<\/p>\n<p><!--more-->Per capire cosa significhi la sigla del titolo, che assomiglia tanto a una crittografia, bisogna fare alcuni passi indietro. Come penso sappiate dalle barzellette sulla categoria, il matematico \u00e8 solo interessato a scoprire se la soluzione al problema esiste; al pi\u00f9 cerca di dimostrare che \u00e8 unica. Possiamo avere alcune categorie particolari di matematici; i logici vorranno magari essere certi che il problema sia decidibile, mentre i costruttivisti vogliono essere certi che la soluzione sia computabile, cio\u00e8 esista un algoritmo che prima o poi termini. Ma qui ci si ferma: che ci vogliano dieci, mille, un milione di o anche un <a href=\"http:\/\/it.wikipedia\/org\/wiki\/Numero_di_Skewes\">numero di Skewes<\/a> di operazioni \u00e8 irrilevante. Ma per gli informatici, che i conti li fanno davvero (beh, li fanno fare ai computer, ma il concetto \u00e8 quello) la cosa \u00e8 ben diversa.<\/p>\n<p>A dirla tutta, nemmeno gli informatici sono poi cos\u00ec interessati al numero <b>esatto<\/b> di operazioni, e preferiscono avere una stima sufficientemente generica che indichi come il numero di operazioni cresca al crescere dei dati di partenza; \u00e8 ovvio che ordinare mille elementi \u00e8 pi\u00f9 lungo che ordinarne dieci, ma <i>quanto<\/i> \u00e8 pi\u00f9 lungo? Per definire il &#8220;quanto&#8221; si usa il concetto di ordine di grandezza, o pi\u00f9 precisamente la &#8220;notazione O grande&#8221;. Data una dimensione di dati di input <i>n<\/i>, si dice che (la complessit\u00e0 di) un algoritmo \u00e8 O(f(<i>n<\/i>)) se il numero di operazioni necessarie per eseguirlo \u00e8 un multiplo di f(<i>n<\/i>) pi\u00f9 altra roba che all&#8217;infinito &#8220;conta di meno&#8221;. Se per esempio un algoritmo richiedesse 5<i>n<\/i><sup>3<\/sup>+1000000<i>n<\/i><sup>2<\/sup>+10<sup>20<\/sup> operazioni, si dice che \u00e8 O(<i>n<\/i><sup>3<\/sup>), anche se per <i>n<\/i>=1000 il termine che conta \u00e8 quello costante. Ah: se si parla di algoritmi numerici, storicamente si considera il numero di moltiplicazioni necessarie, e non ci si preoccupa delle addizioni che nei primi computer erano molto pi\u00f9 semplici da eseguire delle moltiplicazioni. Ma queste sono minuzie. Per fare un esempio pratico, i migliori algoritmi per ordinare <i>n<\/i> elementi richiedono O(<i>n<\/i> log <i>n<\/i>) operazioni, e si \u00e8 anche dimostrato che quello \u00e8 il limite teorico; si potr\u00e0 diminuire il numero effettivo di operazioni, ma saranno sempre grosso modo quelle l\u00ec.<\/p>\n<p>Possiamo finalmente arrivare alla nostra notazione iniziale. I problemi per cui \u00e8 noto un algoritmo per risolverli che richiede un numero polinomiale di operazioni fanno parte della classe P, che sta appunto per &#8220;polynomial&#8221;. Esempi di questi algoritmi sono l&#8217;ordinamento di <i>n<\/i> numeri, oppure il prodotto di due matrici <i>n<\/i>*<i>n<\/i>, il cui <a href=\"http:\/\/en.wikipedia.org\/wiki\/Coppersmith\u2013Winograd_algorithm\">algoritmo record attuale<\/a> richiede O(<i>n<\/i><sup>2.376<\/sup>) operazioni. Ci sono poi alcuni problemi teorici che si sa essere intrinsecamente difficili e richiedere un numero di operazioni che cresce esponenzialmente con <i>n<\/i>; questi fanno parte della classe EXP. Visto che <i>e<sup>n<\/sup><\/i> cresce pi\u00f9 in fretta di <i>n<sup>k<\/sup><\/i> per qualunque <i>k<\/i>, problemi di questo tipo sono intrinsecamente tosti, ma come ho detto non capitano in pratica. C&#8217;\u00e8 poi un&#8217;altra categoria di problemi, chiamati appunto NP; la sigla non sta per &#8220;non polynomial&#8221;, come si potrebbe pensare, ma per <b>non deterministic polynomial<\/b>. <\/p>\n<p>Che significa? Fino a ieri, significava che non sono noti algoritmi di complessit\u00e0 polinomiale per risolverli, ma che sarebbe possibile risolverli in tempo polinomiale se avessimo un computer non deterministico. Il modo pi\u00f9 semplice per capire questa definizione \u00e8 immaginare l&#8217;Algoritmo di Gastone. Gastone Paperone, essendo per definizione fortunatissimo, ogni volta che deve fare una scelta trova sempre quella giusta; in questo modo evita tutti i passi falsi e arriva alla soluzione di un problema NP in tempo polinomiale, mentre non solo Paolino Paperino che \u00e8 notoriamente uno sfigato ma anche Qui, Quo, Qua con il loro Manuale delle Giovani Marmotte ci metteranno un tempo esponenziale. Un modo alternativo per definire i problemi NP \u00e8 dire che sono quelli per cui <b>verificare<\/b> la soluzione (se si pone il problema in modo tale che si pu\u00f2 dare una risposta s\u00ec\/no) richiede tempo polinomiale. Per fare un esempio, immaginate di avere un insieme di numeri interi, positivi e negativi, e che vi si chieda se c&#8217;\u00e8 un sottoinsieme la cui somma sia esattamente zero. Per risolvere il problema occorre provare tutti i gruppi di 2, 3, 4, &#8230;  <i>n<\/i> numeri, e quindi il costo computazionale \u00e8 esponenziale, dell&#8217;ordine di 2<sup><i>n<\/i><\/sup>; ma se il vostro nonno vi dice in sogno di provare un ben preciso insieme di numeri, potete vedere in fretta se sono effettivamente una soluzione.<\/p>\n<p>Da decenni gli informatici cercano di capire se le due classi sono identiche, e noi semplicemente non siamo in grado di trovare gli algoritmi buoni per risolvere i problemi NP in tempo polinomiale, o se sono diverse e quindi quei problemi sono davvero difficili. Si \u00e8 scoperta un&#8217;intera classe di problemi, detti NP-completi e che si trovano spesso nella vita reale, per cui &#8220;risolto uno, risolti tutti&#8221;, nel senso che c&#8217;\u00e8 un algoritmo polinomiale che data la soluzione a uno di questi problemi ne ricava una per ciascuno degli altri; ma questo non basta. Se ora effettivamente Delolalikar ha dimostrato che P != NP dobbiamo metterci il cuore in pace; anche quei problemi sono intrinsecamente difficili. Non che la <i>dimostrazione<\/i> sia facile, visto che sembra assembli risultati da branche diversissime della matematica: una dimostrazione insomma non bella, ma utile; utile anche per guadagnare un milione di dollari, visto che questo \u00e8 uno dei <a href=\"http:\/\/www.claymath.org\/millennium\/\">Millennium Problems<\/a>.<\/p>\n<p>Ma poi sarebbe davvero utile? Beh, non proprio. Nella vita reale ci sono algoritmi per la soluzione di problemi NP-completi che danno quasi certamente la soluzione in tempo polinomiale, oppure che terminano quasi sempre in tempo polinomiale; insomma, all&#8217;atto pratico le soluzioni ce le troviamo comunque. Anche il problema attualmente pi\u00f9 importante per tutta la crittografia, quello della fattorizzazione di un numero, potrebbe prima o poi avere una soluzione di questo tipo, anche se personalmente ne dubito. Resta il punto che anche gli esperti di teoria della complessit\u00e0 sono matematici; come dicevo all&#8217;inizio, a loro importa vedere il teorema dimostrato, anche se poi non lo useranno in pratica.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Forse \u00e8 stata dimostrata la congettura pi\u00f9 importante nel campo dell&#8217;informatica: alcuni problemi sono intrinsecamente difficili. In attesa che la comunit\u00e0 matematica accetti o no la dimostrazione, ecco una spiegazione di qual \u00e8 il problema.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2310","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-Bg","jetpack-related-posts":[{"id":2470,"url":"https:\/\/xmau.com\/ilpost\/2012\/01\/09\/sudoku-minimali-e-massimali\/","url_meta":{"origin":2310,"position":0},"title":"Sudoku minimali e massimali","author":".mau.","date":"09\/01\/2012","format":false,"excerpt":"Il 2012 si \u00e8 aperto con la dimostrazione che per avere un sudoku risolvibile \u00e8 necessario avere almeno 17 numeri. Come ci si \u00e8 arrivati? Forza (quasi) bruta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2012\/01\/sudoku77.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2481,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/23\/quando-i-matematici-sbagliano\/","url_meta":{"origin":2310,"position":1},"title":"Quando i matematici sbagliano","author":".mau.","date":"23\/02\/2012","format":false,"excerpt":"Perch\u00e9 preoccuparsi delle smentite in fisica? Persino in matematica una dimostrazione non \u00e8 sempre corretta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":1499,"url":"https:\/\/xmau.com\/ilpost\/2019\/06\/27\/recensione-matematica-per-giovani-menti\/","url_meta":{"origin":2310,"position":2},"title":"Recensione: Matematica per giovani menti","author":".mau.","date":"27\/06\/2019","format":false,"excerpt":"Settantacinque problemi matematici e logici pensati per chi la matematica se la trova davanti pi\u00f9 di quanto vorrebbe.","rel":"","context":"In \"libri\"","block_context":{"text":"libri","link":"https:\/\/xmau.com\/ilpost\/tag\/libri\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/06\/9788822068842.jpg?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2450,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/16\/esercizi-o-problemi\/","url_meta":{"origin":2310,"position":3},"title":"Esercizi o problemi?","author":".mau.","date":"16\/09\/2011","format":false,"excerpt":"Sappiamo che non esiste una via regia per la matematica, e che bisogna mettersi a faticare per ottenere dei risultati. Ma c'\u00e8 modo e modo di faticare: svolgere esercizi o risolvere problemi sono due attivit\u00e0 ben diverse.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2478,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/13\/una-dimostrazione-errata-e-meglio-che-nessuna-dimostrazione\/","url_meta":{"origin":2310,"position":4},"title":"Una dimostrazione errata \u00e8 meglio che nessuna dimostrazione","author":".mau.","date":"13\/02\/2012","format":false,"excerpt":"Certo, in matematica una dimostrazione errata di per s\u00e9 non serve a nulla. Per\u00f2 pu\u00f2 essere un utile punto di partenza.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":580,"url":"https:\/\/xmau.com\/ilpost\/2015\/06\/19\/maturita-2015-luci-e-ombre\/","url_meta":{"origin":2310,"position":5},"title":"Maturit\u00e0 2015, luci e ombre","author":".mau.","date":"19\/06\/2015","format":false,"excerpt":"Ottima l'idea di avere un esempio pratico, meno buona quella di un quesito \"facile\" troppo generico","rel":"","context":"In \"dematematizzazione\"","block_context":{"text":"dematematizzazione","link":"https:\/\/xmau.com\/ilpost\/tag\/dematematizzazione\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2310","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2310"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2310\/revisions"}],"predecessor-version":[{"id":2311,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2310\/revisions\/2311"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2310"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}