Algoritmi e fenomeni emergentiComplessità computazionale

P contro NP

Una domanda da un milione di dollari: trovare è più difficile che verificare?

Un milione di dollari aspetta chi risponderà a una domanda sui rompicapi. Perché nessuno l'ha riscosso dal 2000?

Scoprirai

  • Che cosa significa «veloce» per un computer
  • Perché una risposta abbatterebbe la cifratura
  • Su cosa scommette la maggioranza degli esperti

Perché conta

La crittografia della tua banca, i giri di consegna e persino la matematica dipendono da questo: trovare è davvero più difficile che verificare?

Circa 4 min7 schermate interattive · 5 domandeLezione 657 · Zona 73

Gioca questa lezione

Gratis nel browser o su iPhone

Altro in questa zona

  1. 649NumeriI logaritmiPerché terremoti e suono usano scale strane
  2. 650Ingegneria biomedicaLa mano comandata dalla menteI segnali dei muscoli possono muovere una mano artificiale
  3. 651TopologiaLa bottiglia di KleinUna bottiglia senza interno che non può esistere nel nostro mondo
  4. 652Fondamenti di probabilitàIl paradosso di BertrandUna domanda su una linea casuale ha tre risposte giuste
  5. 653Storia del softwareLinux era «solo un hobby»Il progetto personale di uno studente oggi gira sulla maggior parte dei server del mondo
  6. 654Provenienza dei contenutiLa filigrana dell'IAI contenuti generati possono portare indizi nascosti sulla loro origine
  7. 655Esplorazione spazialeIl pallido puntino bluLa Terra vista da 6 miliardi di chilometri è un granello in un raggio di sole
  8. 656Complessità computazionaleFacile da verificare, difficile da risolvereVerificare un sudoku richiede secondi; risolverlo può richiedere un'eternità