Algoritmi e fenomeni emergentiComplessità computazionale

Facile da verificare, difficile da risolvere

Verificare un sudoku richiede secondi; risolverlo può richiedere un'eternità

Trovare un errore in un sudoku finito richiede pochi secondi. Allora perché riempire la stessa griglia può costarti un'ora?

Scoprirai

  • Quanti pochi passi bastano per verificare
  • Perché risolvere richiede tante ipotesi
  • Il puzzle da 2 milioni di dollari mai finito

Perché conta

Orari, consegne e rompicapi condividono tutti questo divario, che porta a una delle più grandi domande aperte della matematica.

Circa 3 min6 schermate interattive · 5 domandeLezione 656 · 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. 657Complessità computazionaleP contro NPUna domanda da un milione di dollari: trovare è più difficile che verificare?