• In questa pagina trovate:
• Aprile: il mese della matematica!
• In onore di π
• Il Teorema di Green - Tao : Esistono progressioni aritmetiche di primi di qualsiasi lunghezza!
• Il più grande numero primo noto
• Infiniti
• Complessità computazionale e giochi veramente difficili

6 Aprile 2006

Mathematics Awareness Month

Da sempre la matematica ha un rapporto privilegiato, di vicendevole scambio, con la fisica. Il tentativo - riuscito in maniera incredibilmente efficace - di descrivere il mondo attraverso equazioni matematiche, è di centrale importanza nella nostra cultura. I risultati di questa fruttuosa relazione sono ben noti.

Per il fisico:

• La formula matematica permette di dominare tutti i casi particolari che si presentano.
  
• Le soluzioni non previste di una equazione possono suggerire la possibilità di nuovi scenari nel mondo reale, bisognosi a loro volta di spiegazione fisica.
  

• I risultati eterogenei degli esperimenti fisici richiedono una interpretazione matetematica unificante, stimolando la ricerca.
• Le nuove visioni del mondo scoperte dalla fisica suggeriscono sovente la necessità di nuove teorie matematiche.

Con la nascita della informatica moderna, dai tempi di Turing, Shannon, e von Neumann, si è creato un nuovo rapporto, ricco di profondi risultati (vedi per esempio la dimostrazione della indecidibilità del problema dell'arresto) e di sorprendenti e inaspettate applicazioni della matematica, come la crittografia.

Quando utilizziamo il computer di casa, collegato alla rete, per fare acquisti, per eseguire trasferimenti di denaro o ricaricare il cellulare dobbiamo comunicare password, numeri di carte di credito, numeri di telefono o altri dati riservati. Il possesso di queste informazioni da parte di malintenzionati può essere assai pericoloso. Per questo, durante lo svolgimento di operazioni delicate, la connessione viene effettuata in una modalità particolare, protetta da sofisticati sistemi crittografici, basati su algoritmi matematici.

Un nuovo campo di applicazione della matematica, contiguo alla crittografia, è il voto elettronico. La matematica permette la creazione di protocolli atti a garantire la segretezza, la certezza, l'onestà e la libertà delle votazioni telematiche.

A questi e ad altri argomenti simili è dedicato il MAM di Aprile 2006 (MAM = "Mathematics Awareness Month") promosso dalle "American Mathematical Society", "American Statistical Association", "Mathematical Association of America" e "Society for Industrial and Applied Mathematics". Precisamente il titolo del MAM 2006 è "Mathematics and Internet Security".

La funzione del MAM è quella di rendere il grande pubblico sempre più consapevole della importanza della matematica, e del fatto che essa è presente in tutte le attività umane.

Il MAM si celebra esattamente da 20 anni, dal 1986. Ha trattato i temi più diversi. Molte edizioni hanno lasciato tracce interessanti, articoli, documenti e immagini. Volete vivere una bella avventura? Visitate il MAM 2003, dedicato a Matematica e Arte!

Il bellissimo logo di MAM 2003

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

11 Marzo 2006

Ogni anno negli USA, presso l'Exploratorium di San Francisco si celebra il Pi Day. La data della festa è il 3.14 (14 marzo) alle ore 1:59 precise.

Si tratta di una lodevolissima iniziativa, alla quale desideravo da tempo associarmi, se pur virtualmente. Guardando in giro sulla rete ho scoperto che ci ha già pensato il Professor Federico Peiretti, sul bellissimo sito del Progetto Polymath, che consiglio a tutti di visitare.
Si tratta di un argomento inesauribile, al quale spero di poter dedicare in futuro una apposita sezione. Pi greco appare, come per miracolo, del tutto inaspettato, nelle situazioni più diverse. Parleremo per cominciare di uno straordinario incotro tra π e il "maestro di tutti noi", Leonhard Euler (1707 - 1790).

1 - Serie

La serie "madre" è la serie geometrica, che abbiamo già incontrato nell'articolo sulla Sezione aurea e numeri di Fibonacci.

Diciamo serie geometrica la serie:

∞ ∑ n = 0

xn

= 1 + x + x2 + x3 + ... + xn + ...

1.1 La serie geometrica converge per ogni x tale che |x| < 1, e la sua somma è 1/(1-x).

Per esempio se x = 1/2 da 1.1 si ricava che:

1 + 1/2 + 1/4 + 1/8 +1/16 + 1/32 + ... = 2

1.2 Ricordiamo che, data una serie generica:

∞ ∑ n = 0

an

si dice che essa converge ad α, o, equivalentemente, che la sua somma è α se la successione delle somme parziali

S₀ = a₀, S₁ = a₀ + a₁, S₂ = a₀ + a₁ + a₂, ...

converge ad α. Pertanto la somma della serie è α se, dato un qualsiasi ε > 0, esiste un indice m tale che per ogni n > m si ha

|α - S_n| < ε
ovvero:

lim n→∞

|α - Sn|

= 0

E' facilissimo dimostrare 1.1.

|α - Sn| = |1/(1-x) - Sn| = |1/(1-x) - (1 + x + x2 + x3 + ... + xn-1)| = |1/(1-x) - (1-xn)/(1-x)| = |xn/(1-x)| = |1/(1-x)| |xn|. Poiché per ipotesi |x| < 1, il limite per n che tende all'infinito di |x|n è 0, e segue la tesi.

Oltre alla serie geometrica, un'altra serie da tenere sempre sottomano è la serie armonica:

∞ ∑ n = 1

1/n

La serie armonica diverge, cioè:

lim n→∞

(1 + 1/2 + 1/3 + ... + 1/n)

= ∞

Questo fatto può essere visto facilmente raggruppando gli elementi in modo opportuno:

1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + ... =
1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + 1/8) + ... >
1 + 1/2 + (1/4 + 1/4) + (1/8 + 1/8 + 1/8 + 1/8) + ... =
1 + 1/2 +     1/2     +           1/2           + ...  

N.B. Quando i termini di una serie non sono tutti positivi non si possono, in generale, utilizzare le proprietà associativa e commutativa.

1.3 (Eulero)

Per n che tende all'infinito la differenza

n ∑ k = 1

1/k

- log(n)

tende alla costante γ = 0,577215664901532860606512090083..

Abbiamo visto sopra che, per n = 1000000, la somma parziale della serie armonica vale circa 14,3927. Calcolando il logaritmo corrispondente log(10⁶) si ottiene circa 13.8155. In effetti la differenza di questi valori dà 0,5772.

γ è detta costante di Eulero (o anche costante di Eulero - Mascheroni).

1.4 Congettura
γ è irrazionale.

Sembra incredibile, ma fino ad oggi, anche se tutti ci credono, nessuno è riuscito a provare che γ non è il rapporto di due numeri interi!

Jakob Bernoulli dimostrò che la serie dei reciproci dei numeri triangolari, converge, al contrario della serie armonica.

1.5 (Jakob Bernoulli)

1 + 1/3 + 1/6 + 1/10 + 1/15 + ... = 2

Dimostrazione

Ricordiamo che l'n-esimo numero triangolare è n(n+1)/2. Osserviamo che 1/n - 1/(n+1) = 1/(n(n+1)). Si ha allora:

1 + 1/3 + 1/6 + 1/10 + 1/15 + ... = 2 [1/2 + 1/6 + 1/12 + 1/20 + 1/30 + ...] =
2 [1/2 + (1/2 - 1/3) + (1/3 - 1/4) + (1/4 - 1/5) + ...] = 2 [1/2 + 1/2] = 2.

Questa tecnica di calcolo, che si può utilizare con certi tipi di serie, si chiama "telescopica".

• La serie dei reciproci degli interi diverge.
• La serie dei reciproci dei numeri triangolari converge ed ha come somma 2.

1.6 Teorema
La serie

∞ ∑ n = 1

1/n2

converge.

Dimostrazione.

Bernoulli utilizzò quello che oggi viene detto "criterio del confronto".
Poiché 2 n² > n² + n, si ha che n² > n(n+1)/2 e infine
1/n² < 1/(n(n+1)/2).

Ora, la serie "triangolare" converge a 2. Ogni termine della serie "quadrata" è minore del corrisponedente termine della serie "triangolare". Pertanto anche la serie "quadrata" converge, e converge ad un α non maggiore di 2.

Con suo grande disappunto, Jakob Bernoulli non riuscì a rispondere a questa domanda.

2 - Eulero

Nel 1735 Eulero scriveva con gioia:

Ora però, contro ogni aspettativa, ho trovato una espressione elegante per la somma della serie 1 + 1/4 + 1/9 + 1/16 + etc., che dipende dalla quadratura del cerchio ... Ho trovato che sei volte la somma di questa serie è uguale al quadrato della circonferenza di un cerchio di diametro 1.

Come era arrivato a questo fantastico risultato? Da dove salta fuori π?

Eulero sapeva che sen x si sviluppa in serie di potenze così:

2.1 sen x = x - x³/3! + x⁵/5! - x⁷/7! + x⁹/9! - ...

2.2 Consideriamo un polinomio f(x) di grado n tale che f(0) = 1 , e siano α₁, α₂, ... , α_n i suoi zeri. Allora posto

g(x) = (1 - x/α₁)(1 - x/α₂) ... (1 - x/α_n-1)(1 - x/α_n)

si ha f(x) = g(x).

Questo fatto è evidente perché g(x) è un polinomio di grado n, g(0) = f(0) = 1, e g(α_i) = 0, per ogni i compreso tra 1 ed n.

2.3 f(x) = (sen x)/x = 1 - x²/3! + x⁴/5! - x⁶/7! + x⁸/9! - ...

Applicando la 2.2 Eulero ottiene che:

Posto

g(x) = (1 - x/π)(1 - x/(-π))(1 - x/2π)(1 - x/(-2π))...(1 - x/kπ)(1 - x/(-kπ))...

si ha f(x) = g(x).

2.4 f(x) = (1 - x²/π²)(1 - x²/(4π²))(1 - x²/(9π²))(1 - x²/(16π²)) ... (1 - x²/(k²π²)) ...

2.5 f(x) = 1 - (1/(π²) + 1/(4π²) + 1/(9π²) + 1/(16π²) + ... ) x² + ( ... ) x⁴ + ....

2.6   -1/3! = -1/π² (1 + 1/4 + 1/9 + 1/16 + ... )

Il reciproco di π²/6 è:

6/π² = 0,60792710185402662866327677925836583342615264803347929...

2.7  6/π² è la probabilità che due interi scelti a caso siano coprimi

(Ricordiamo che "coprimi" equivale a "non hanno in comune fattori diversi da 1")

Nella successione degli interi positivi un numero su n è divisibile per n (lapalissiano, vero?). Quindi la probabilità che un numero sia divisibile per p è 1/p. Se i numeri sono due, la probabilità che entrambi siano divisibili per p è 1/p² e dunque quella che non siano entrambi divisibili per p risulta essere (1 - 1 /p²). Due numeri sono coprimi se e solo se per ogni primo p, p non li divide entrambi.

Pertanto, se denotiamo con p₁, p₂, p₃, ... , p_n, ... la successione dei numeri primi, la probabilità Prob che due interi siano coprimi risulta essere il prodotto di tutte le probabilità (1 - 1 /p_j²), ovvero:

2.8

Prob =

∞ ∏ j = 1

(1 - 1/pj2)

Per calcolare il valore del prodotto infinito 2.8 utilizziamo la famosa e utilissima "formula del prodotto" (valida per ogni s maggiore di 1), dimostrata da Eulero nel 1737:

2.9

P(s) =

∞ ∏ j = 1

(1 - 1/pjs) -1

=

∞ ∑ n = 1

1/ns

Ponendo s = 2 nella 2.9 otteniamo che P(2) è uguale alla somma dei reciproci dei quadrati, dunque (lo sappiamo bene...)

P(2) = π²/6

Confrontando la 2.8 e la 2.9 si osserva che P(2) è il reciproco di Prob, cioè

2.10  Prob = 6/π²

che è la 2.7.

Concludendo: buona Festa del Pi Greco e a presto!

Riferimenti

William Dunham - Euler, the Master of Us All - The Mathematical Association of America - The Dolciani Math. Exposition N° 22

The MacTutor History of Mathematics archive

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

3 Febbraio 2006

TRANSIRE SUUM PECTUS MUNDOQUE POTIRI

Tra i possibili vincitori si fanno i nomi di Ben Green e di Terence Tao, coautori dell'articolo "The primes contain arbitrarily long arithmetic progressions" (2004-2005). Si tratta di un conseguimento di enorme portata, sia per il risultato in sè - che ha dell'incredibile - sia per i metodi utilizzati, che aprono nuovi campi ri ricerca.

Da sempre si sono cercate particolari sequenze di numeri primi. Tra le più interessanti vi sono certamente le progressioni aritmetiche:

[1] a, a + d, a + 2d, ... , a + (k-1)d

[2.1]
valore iniziale = 3
lunghezza = 10
differenza = 4
3, 7, 11, 15, 19, 23, 27, 31, 35, 39

[2.2]
valore iniziale = 5
lunghezza = 12
differenza = 7
5, 12, 19, 26, 33, 40, 47, 54, 61, 68, 75, 82

[2.3]
valore iniziale = 47
lunghezza = 7
differenza = 210
47, 257, 467, 677, 887, 1097, 1307

47, 179, 199, 409, 619, 829, 881, 1091, 1453, 3499, 3709, 3919, 
10529, 10627, 10837, 10859, 11069, 11279, 14423,20771, 22697,30097,
30307, 31583, 31793, 32363, 41669, 75703, 93281 , 95747, 120661,
120737, 120871, 120947, 129287, 140603, 153319, 153529, 182537,
182747, 205187, 217351, 269713, 422129, 456349, 471089, 471299,
487391, 487601, 504607, 519919, 564973, 565183, 565393, 586291,
590813, 635309, 724099, 733847, 825991, 826201, 844087, 857453,
865591, 867409, 934253, 980431, 1010747, 1010957, 1022891, 1253849,
1277761, 1280623, 1280833, 1288607, 1288817, 1289027, 1290161, 1299079,
1302281, 1302491, 1302701, 1308077, 1395209, 1395419, 1395463, 1398763,
1420091, 1470659, 1548947, 1603471, 1839697, 1870619, 1952413, 1982599,
1982809

[3] 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089

In (GT) Ben Green e Terence Tao hanno dimostrato che:

Teorema di Green - Tao

Esistono (infinite) PAP di lunghezza k per ogni intero k positivo.

[5] PAP di lunghezza 23
valore iniziale: 56211383760397
lunghezza : 23
differenza : 44546738095860
56211383760397,  100758121856257, 145304859952117, 189851598047977,
234398336143837, 278945074239697, 323491812335557, 368038550431417,
412585288527277, 457132026623137, 501678764718997, 546225502814857,
590772240910717, 635318979006577, 679865717102437, 724412455198297,
768959193294157, 813505931390017, 858052669485877, 902599407581737,
947146145677597, 991692883773457, 1036239621869317

valore iniziale : 11410337850553
lunghezza : 22
differenza : 4609098694200
11410337850553, 16019436544753, 20628535238953, 25237633933153,
29846732627353, 34455831321553, 39064930015753, 43674028709953,
48283127404153, 52892226098353, 57501324792553, 62110423486753,
66719522180953, 71328620875153, 75937719569353, 80546818263553,
85155916957753, 89765015651953, 94374114346153, 98983213040353,
103592311734553, 108201410428753

 4609098694200 = 23 3 52 7 11 17 19 23 1033
 44546738095860 = 22 3 5 7 11 13 17 19 23 99839 

p# = prodotto dei primi £ p

Questo implica che se cerchiamo, per esempio, una PAP di lunghezza 17, la differenza d dovrà essere divisibile per 17# = 510510.
La successione dei primoriali:

2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, ...

Nella tavola sottostante (presa dall'articolo (G) di Andrew Granville) appaiono le PAP, con lunghezza compresa tra 3 e 21, che hanno l'ultimo termine minimo. Questo significa che, prendendo per esempio k = 13, non esistono PAP di lunghezza 13 il cui ultimo termine sia minore di 725663.

Le PAP di lunghezza k compresa tra 3 e 21 con ultimo termine minimo. (Da (G))

Il primo risultato importante sulle PAP si ebbe nel 1939, quando van der Corput dimostrò che esistono infinite PAP di lunghezza 3. Non accadde nulla di rilevante fino al 1981, anno in cui Heath Brown dimostrò che esistono infinite PA di lunghezza 4, nelle quali 3 elementi sono primi e uno è "quasi primo", con il ché si intende un intero che sia primo o prodotto di due primi.

Alla fine degli anni 80 Balog, procedendo in una direzione diversa ma molto interessante, dimostrò questo fatto:

Teorema di Antal Balog

Dato un qualsiasi intero k maggiore di 1, esistono infiniti insiemi A tali che:

• A contiene k elementi, tutti primi
• presi due elementi qualunque p e q in A, l'intero (p + q)/2 è primo

Con una breve ricerca al computer ho trovato due insiemi di Balog di 9 elementi:

A = {5, 29, 53, 89, 113, 449, 17609, 25793, 82373}

L'isieme MA delle 36 medie contiene 34 primi distinti:

MA = {17, 29, 41, 47, 59, 71, 83, 101, 227, 239, 251, 269, 281, 8807, 8819, 8831,
8849, 8861, 9029, 12899, 12911, 12923, 12941, 12953, 13121, 21701, 41189,
41201, 41213, 41231, 41243, 41411, 49991, 54083}

B = {7, 19, 67, 127, 547, 607, 6619, 126127, 345979}

L'insieme MB delle 36 medie contiene 34 primi distinti:

MB = {13, 37, 43, 67, 73, 97, 277, 283, 307, 313, 337, 367, 577, 3313, 3319, 3343,
3373, 3583, 3613, 63067, 63073, 63097, 63127, 63337, 63367, 66373, 172993,
172999, 173023, 173053, 173263, 173293, 176299, 236053}

Green e Tao non sono arrivati a questi straordinari risultati per caso o per una subitanea illuminazione. Si tratta di un lavoro paziente, lungo e pianificato con cura. E naturalmente di capacità e di cultura matematica eccezionali.

Ben Green (nato a Bristol nel 1977) ha rappresentato l'Inghilterra in due Olimpiadi Matematiche (1994 e 1995). Nel 1995 entrò al Trinity College, sotto la direzione di William Timothy Gowers (che nel 1998, a 35 anni, vincerà la medaglia Fields). Dopo avere conquistato il leggendario "Certificate of Advanced Study in Mathematics" di Cambridge, si dedicò allo studio delle tecniche che Gowers aveva sviluppato per dare una nuova dimostrazione del famoso teorema di Szemerédi:

Teorema di Szemerédi

Ogni insieme di interi positivi che ha densità non nulla in N contiene PA di qualsiasi lunghezza.

Terence Tao (nato a Adelaide nel 1975) ottenne il PhD dalla Università di Princeton a soli 21 anni. Dall'età di 24 anni è "full professor" di Matematica presso l'università della California (UCLA). Viene considerato un "Mozart" della Matematica. Essa fluisce da lui apparentemente senza sforzo. Tao somiglia ai grandi del passato, perché i suoi interessi non sono limitati ad un solo settore della Matematica; egli si muove agilmente in campi assai diversi, dalla Geometria Algebrica, alla Combinatoria, Teoria Ergodica, Teoria dei Numeri e Analisi Armonica.

Le ricerche di Green e Tao ad un certo punto incontrarono un ostacolo che sembrava difficilmente superabile. Fortunatamente esisteva proprio lo strumento che a loro serviva per uscire dall'intoppo, un teorema dimostrato poco prima da Dan Goldston e Cem Yildirim nel loro lavoro sui Gaps tra i numeri primi. La prima versione dell'articolo di Goldston e Yildirim conteneva una inesattezza, che venne poi corretta, con l'aiuto di Yanos Pintz: il risultato finale (verificato da Yoichi Motohashi) segna un altro avanzamento storico degli ultimi anni nella Teoria dei Numeri:

Teorema sui gaps tra i numeri primi di Dan Goldston, Cem Yildirim e Yanos Pintz (GYP)

Diciamo p₁, p₂, ... p_n ... la successione dei numeri primi. Dato un ε qualsiasi maggiore di 0

esistono infiniti n tali che p_n+1 - p_n < ε log p_n

Ma torniamo a Green e Tao. Come racconta lo stesso Green l'incontro con Andrew Granville fu un vero colpo di fortuna. Granville aveva letto il preprint di Goldston e Yildirim, ed era convinto che lì avrebbero trovato quello di cui avevano bisogno. Aveva ragione! Attenzione però, la fortuna è solo un elemento del successo, in Matematica come in tutte le attività umane. Penso che la descrizione che Terence Tao fa del suo lavoro sia molto interessante, e dovrebbe essere meditata dai tanti che credono che problemi rimasti insoluti da secoli si possano risolvere con un "lampo di genio". Ecco le sue parole:

"La maggior parte dei matematici che affrontano un problema, cercheranno di risolverlo direttamente. Anche quando ci riescono, non è detto che abbiano ottenuto una piena comprensione di quanto hanno fatto. Prima io esamino tutti i dettagli e elaboro una stategia. Una volta che ho una strategia, un problema molto complicato si può spezzare in un insieme di molti mini-problemi. ( ... )
Non è tanto una questione di essere abili o veloci. E' piuttosto come scalare una parete. Certamente è utile essere molto forti e agili, e avere tanta corda. Ma l'importante è individuare un percorso che consenta di arrivare fin lassù. Fare i calcoli in fretta e sapere tante cose è come scalare una roccia essendo forti, agili e muniti di buoni attrezzi. Però quello che ancora manca è un piano - è questa la parte difficile - e per averlo occorre una visione d'insieme."

(B) Antal Balog, "The prime k-tuplets conjecture on average", Analytic Number Theory (eds. B.C. Berndt et. al), Birkhäuser, Boston, (1990), 165-204
(FJU) Markus Frind, Paul Jobling e Paul Underwood, "23 primes in arithmetic progression"
(G) Andrew Granville, "Prime Numbers Patterns"
(GT) Ben Green, Terence Tao - "The primes contain arbitrarily long arithmetic progressions" - inviato per la pubblicazione agli "Annals of Mathematics"
(MPT) A. Moran, P. Pritchard e A. Thyssen. "Twenty-two primes in arithmetic progression", Math. Comp., 64 (1995), 1337-1339.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

13 Gennaio 2006

Da molti anni accade che il più grande numero primo noto sia un primo di Mersenne. Chi volesse capovolgere la situazione, e trovare un numero primo "generico" più grande dovrà ancora una volta alzare il tiro (e di parecchio).

Il 42-esimo primo di Mersenne ha "appena" 7.816.230 cifre, e sembra piccolo posto accanto al nuovo arrivato.

Il più recente primo di Mersenne (il 43-esimo) è stato scoperto il 15 Dicembre 2005 da Curtis Cooper e Steven Boone :

M = 2^30.402.457 - 1 è il più grande numero primo noto, con ben 9.152.052 cifre! Siamo a un passo dalla soglia dei 10 milioni di cifre, per la quale la Electronic Frontier Foundation offre 100.000 dollari.

Il premio precedente - di 50.000 dollari - è stato assegnato nel 2000 a Nayan Hajratwala il quale, partecipando alla GIMPS, trovò nel 1999 il 38-esimo primo di Mersenne (2.098.960 cifre).

A M corrisponde il 43° numero numero perfetto pari:

Curtis Cooper e Steven Boone sono docenti presso la Central Missouri State University (CMSU) e partecipano da anni alla GIMPS (Great Internet Mersenne Prime Search).

I due professori (e la CMSU) si sono ampiamente meritato il record mondiale che hanno ottenuto: coordinano il lavoro di ben 700 computers. Si tratta però di una impresa collettiva, che da soli non avrebbero potuto realizzare.
In base a questa considerazione, la scoperta sarà attribuita a "Cooper, Boone, Woltman, Kurowski, et al".
Gli altri sono le decine di migliaia di volontari che partecipano alla GIMPS.

GIMPS è un progetto gestito da PrimeNet, un sistema di calcolo parallelo distribuito in rete a livello mondiale, creato nel 1997 da Scott Kurowski, basato sulla medesima tecnolgia di Entropia, impresa fondata Kurowski stesso.

Nel momento in cui scrivo il server di PrimeNet connette 71720 computers, che eseguono qualcosa come 19442 gigaflops al secondo, con una potenza di calcolo pari a quella di 342 supercomputer Cry T932.

Chiunque può unirsi alla ricerca, è sufficiente scaricare il software necessario, ovviamente gratuito. Il bello è che l'utente non si accorge nemmeno di averlo, perché funziona solo quando la CPU non è impegnata a fare altro.

La parte più interessante del software è di George Woltman (che fondò GIMPS nel gennaio del 1996), il quale ha implementato in linguaggio macchina un sofisticato algoritmo di Richard Crandall, che consente di eseguire velocemente i quadrati necessari per dimostrare la primalità dei numeri di Mersenne. Si tratta di moltiplicare numeri di milioni di cifre. L'algoritmo è descritto - tra mille altri affascinanti risultati - nel bellissimo libro che Crandall ha scritto con Carl Pomerance: "Prime numbers, a computational perspective" (edito dalla casa editrice Springer).

Per stabilire la primalità dei numeri di Mersenne si utilizza il Criterio di Lucas - Lehmer:

Dato un intero n maggiore di 2:
M_n = 2ⁿ - 1 è primo se e solo se M_n divide L_n-1, dove
L₁ = 4 e, per ogni k maggiore di 1, L_k = L_k-1² - 2.

4, 14, 194, 37634, 1416317954, 2005956546822746114, 4023861667741036022825635656102100994

Esempio

Denotiamo con L la successione {L1, L2, L3, ... L22}
***
M3 = 7
L mod M3 = {4,0,5,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}
0 al posto 2, OK
***
M5 = 31
L mod M5 = {4,14,8,0,29,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}
0 al post 4, OK
***
M7 = 127
L mod M7 = {4,14,67,42,111,0,125,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}
0 al posto 6, OK
***
M11 = 2047
L mod M11 = {4,14,194,788,701,119,1877,240,282,1736,510,129,263,1616,1529,165,612,1988,1432,1575,1706,1647}
Non c'è zero al posto 10, M11 non è primo
***
M13 = 8191
L mod M13 = {4,14,194,4870,3953,5970,1857,36,1294,3470,128,0,8189,2,2,2,2,2,2,2,2,2}
0 al posto 12, OK
***
M17 = 131071
L mod M17 = {4,14,194,37634,95799,119121,66179,53645,122218,126220,70490,69559,99585,78221,130559,0,131069,2,2,2,2,2}
0 al posto 16, OK
***
M19 = 524287
L mod M19 = {4,14,194,37634,218767,510066,386344,323156,218526,504140,103469,417706,307417,382989,275842,85226,523263,0,524285,2,2,2}
0 al posto 18, OK
***
M23 = 8388607
L mod M23 = {4,14,194,37634,7031978,7033660,1176429,7643358,3179743,2694768,763525,4182158,7004001,1531454,5888805,1140622,4321431,7041324,2756392,1280050,6563009,6107895}
Non c'è 0 al posto 22, M23 non è primo
***

V0 = 2
V1 = 4
Per ogni t maggiore di 2:
Vt = 4 Vt-1 - Vt-2

Lk = V2k-1 per ogni intero k positivo.

Qui si trova l'elenco dei 43 primi di Mersenne noti.

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

9 Novembre 2005

Aleph 1 - di Justin Mullins

§1 - I numeri cardinali

Tutto ciò che possiamo contare è finito. Dunque l'infinito non riguarda esclusivamente la nostra capacità di contare, è un qualcosa che si protende anche al di là del calcolo, e riguarda specialmente i numeri in sé, la "numerosità".

Come fa un pastore che non sa contare ad essere sicuro, quando riporta nel recinto le sue pecore, di non averne persa alcuna? Potrebbe agire così: fa uscire le pecore ad una ad una dalla recinzione, e per ognuna di esse mette un sassolino in una borsa. A sera esegue il procedimento contrario: getta una pietruzza e fa entrare un animale. Ha creato, inconsapevolmente, una corrispondenza biunivoca tra l'insieme dei sassi e quello delle pecore.

Se il pastore possiede 15 pecore, egli non conosce il numero 15, ma è in grado di constatare se in un certo insieme ci sono 15 elementi. Può pensare, per esempio, "Ho tante mele quante pecore". Potrebbe facilmente trarre conclusioni corrette del tipo "Nel cortile ci sono più pietre di quante siano le mie pecore", oppure "Le dita delle mie mani sono meno delle mie pecore". La cosa si fa interessante.

Introduciamo i concetti fondamentali che ci serviranno nel seguito:

Sia f una funzione assegnata tra due insiemi X e Y (ovvero una legge che ad ogni elemento di X associa un solo elemento di Y).

Un po' di nomenclatura: X si dice dominio della funzione f, mentre Y è il suo codominio.
Se y = f(x), y si dice immagine di x e x si dice controimmagine di y.

Ora le tre definizioni capitali:

Definizione 1 f si dice iniettiva se elementi distinti del dominio hanno immagini distinte.
(Una funzione iniettiva si dice anche iniezione)

Definizione 2 f si dice suriettiva se ogni elemento di Y ha almeno una controimmagine.
(Una funzione suriettiva si dice anche suriezione)

Definizione 3 Si dice che f è una corrispondenza biunivoca se f è sia iniettiva che suriettiva.
(Una corrispondenza biunivoca si dice anche biezione)

Figura 1	Figura 2
Figura 3	Figura 4

Nella Figura 1 si vede una funzione iniettiva ma non suriettiva.
Nella Figura 2 si vede una funzione suriettiva ma non iniettiva.
Nella Figura 3 si vede una funzione non iniettiva e non suriettiva.
Nella Figura 4 si vede una funzione biettiva.

Pratica di nomenclatura
Esaminiamo da vicino la funzione g di Figura 3.
Il dominio è l'insieme {1, 2, 3, 4}.
Il codominio è l'insieme {A, B, C, D}.
Ogni elemento del dominio ha una ed una sola immagine:
dunque si tratta di una funzione.
g(3) = g(4) = A : gli elementi 3 e 4 hanno la stessa immagine:
pertanto g è una funzione non iniettiva.
Alla stessa conclusione si giunge osservando che A possiede due controimmagini.
Poiché C non ha controimmagini g non è suriettiva.

Mediante questa idea gli insiemi si suddividono in classi disgiunte.

Ognuna di queste classi esprime in modo unico una certa "numerosità" che diciamo numero cardinale.

Per esempio ci sarà la classe di tutti gli insiemi che sono in corrispondenza biunivoca con l'insieme delle dita della mia mano. Essa rappresenta un solo concetto, un unico cardinale. Il fatto poi che lo si denoti con 5, cinque, V, |||||, cinq, cinco, five o in altro modo qualsiasi è indifferente.

Dato un qualunque insieme A, questo apparterrà ad una unica classe di equinumerosità, e avrà una cardinalità, ovvero il numero cardinale espresso dalla classe cui A appartiene.

Denoteremo la cardinalità di A con #A.

I numeri naturali sono le cardinalità degli insiemi finiti.

Per esempio se A = {a, e, i, o, u} allora #A = 5.
Se A è l'insieme dei divisori di 12 allora #A = 6.

À₀ si dice cardinalità del numerabile. Un insieme si dice numerabile se può essere messo in corrispondenza biunivoca con N, cioè se ha cardinalità À₀.

L'insieme H = {1, 4, 9, 16, 25, ... } dei quadrati è numerabile? Vediamo che cosa ne pensava Galileo.

Salv.Io suppongo che voi benissimo sappiate quali sono i numeri quadrati, e quali i non quadrati.

Simp. So benissimo che il numero quadrato è quello che nasce dalla moltiplicazione d'un altro numero in se medesimo: e così il quattro, il nove, etc., son numeri quadrati, nascendo quello dal dua, e questo dal tre, in se medesimi moltiplicati.

Salv. Benissimo: e sapete ancora, che sì come i prodotti si dimandano quadrati, i producenti, cioè quelli che si multiplicano, si chiamano lati o radici; gli altri poi, che non nascono da numeri multiplicati in se stessi, non sono altrimenti quadrati. Onde se io dirò, i numeri tutti, comprendendo i quadrati e i non quadrati, esser più che i quadrati soli, dirò proposizione verissima: non è così?

Simp. Non si può dir altrimenti.

Salv. Interrogando io di poi, quanti siano i numeri quadrati, si può con verità rispondere, loro esser tanti quante sono le proprie radici, avvenga che ogni quadrato ha la sua radice, ogni radice il suo quadrato, né quadrato alcuno ha più d'una sola radice, né radice alcuna più d'un quadrato solo.

Simp. Così sta.

Salv. Ma se io domanderò, quante siano le radici, non si può negare che elle non siano quante tutti i numeri, poiché non vi è numero alcuno che non sia radice di qualche quadrato; e stante questo, converrà dire che i numeri quadrati siano quanti tutti i numeri, poiché tanti sono quante le lor radici, e radici son tutti i numeri: e pur da principio dicemmo, tutti i numeri esser assai più che tutti i quadrati, essendo la maggior parte non quadrati. E pur tuttavia si va la moltitudine de i quadrati sempre con maggior proporzione diminuendo, quanto a maggior numeri si trapassa; perché sino a cento vi sono dieci quadrati, che è quanto dire la decima parte esser quadrati; in dieci mila solo la centesima parte sono quadrati, in un millione solo la millesima: e pur nel numero infinito, se concepir lo potessimo, bisognerebbe dire, tanti essere i quadrati quanti tutti i numeri insieme.

Sagr. Che dunque si ha da determinare in questa occasione?

Salv. Io non veggo che ad altra decisione si possa venire, che a dire, infiniti essere tutti i numeri, infiniti i quadrati, infinite le loro radici, né la moltitudine de' quadrati esser minore di quella di tutti i numeri, né questa maggior di quella, ed in ultima conclusione, gli attributi di eguale maggiore e minore non aver luogo ne gl'infiniti, ma solo nelle quantità terminate. E però quando il Sig. Simplicio mi propone più linee diseguali, e mi domanda come possa essere che nelle maggiori non siano più punti che nelle minori, io gli rispondo che non ve ne sono né più né manco né altrettanti, ma in ciascheduna infiniti: o veramente se io gli rispondessi, i punti nell'una esser quanti sono i numeri quadrati, in un'altra maggiore quanti tutti i numeri, in quella piccolina quanti sono i numeri cubi, non potrei io avergli dato sodisfazione col porne più in una che nell'altra, e pure in ciascheduna infiniti? E questo è quanto alla prima difficoltà.

Sagr. Fermate in grazia, e concedetemi che io aggiunga al detto sin qui un pensiero, che pur ora mi giugne: e questo è, che, stanti le cose dette sin qui, parmi che non solamente non si possa dire, un infinito esser maggiore d'un altro infinito, ma né anco che e' sia maggior d'un finito, perché se 'l numero infinito fusse maggiore, v. g., del millione, ne seguirebbe, che passando dal millione ad altri e ad altri continuamente maggiori, si camminasse verso l'infinito; il che non è: anzi, per l'opposito a quanto maggiori numeri facciamo passaggio, tanto più ci discostiamo dal numero infinito; perché ne i numeri, quanto più si pigliano grandi, sempre più e più rari sono i numeri quadrati in esso contenuti; ma nel numero infinito i quadrati non possono esser manco che tutti i numeri, come pur ora si è concluso; adunque l'andar verso numeri sempre maggiori e maggiori è un discostarsi dal numero infinito.

Salv. E così dal vostro ingegnoso discorso si conclude, gli attributi di maggiore minore o eguale non aver luogo non solamente tra gl'infiniti, ma né anco tra gl'infiniti e i finiti.

[Tratto da: Galileo Galilei - Discorsi e dimostrazioni matematiche intorno a due nuove scienze attenenti alla mecanica & movimenti locali - Giornata prima]

Galileo, nel testo sopra citato, asserisce che:

• I quadrati sono tanti quanti i naturali.
• Gli infiniti non si possono in alcun modo confrontare, non solo tra di loro ma nemmeno con i numeri finiti.

La funzione h: N ® H
così definita: per ogni naturale n, h(n) = n2
è una corrispondenza biunivoca.
E' iniettiva, in quanto interi positivi diversi hanno quadrati diversi.
E' suriettiva, perché ogni quadrato ha una radice quadrata.

Ne segue che #H = #N = À0.

§2 - I cardinali sono ordinati

Ci servono alcune premesse, tratte dalla Teoria degli Insiemi.

Nel seguito A e B sono due insiemi.

1 - Definizione
A e B si dicono equipotenti se tra di essi esiste una corrispondenza biunivoca

2 - Proposizione (ovvia conseguenza delle definizioni date)
A è equipotente a B se e solo se #A = #B

3 - Proposizione
Esiste una iniezione f: A ® B se e solo se esiste una suriezione g: B ® A

4 - Definizione
Diciamo che #A £ #B se esiste una iniezione f: A ® B

5 - Teorema
1) #A £ #A
2) Se #A £ #B e #B £ #C allora #A £ #C
3) Se #A £ #B e #B £ #A allora #A = #B

Le dimostrazioni di 5 1) e di 5 2) sono facili.
La 5 2) asserisce banalmente che:

se esiste una iniezione f: A ® B 
e  esiste una iniezione g: B ® C 
allora esiste una iniezione h: A ® C.

La 5 3) invece afferma che:

se esiste una iniezione f: A ® B 
e  esiste una iniezione g: B ® A 
allora esiste una biezione h: A ® B.

La dimostrazione di questo fatto è difficile.
Il teorema venne congetturato da Cantor e fu provato, indipendentemente, da Schroeder e Bernstein intorno al 1890.

6 - Definizione
Diciamo che #A < #B se #A £ #B ma non vale #B £ #A

Le condizioni 5 1), 2) e 3) sono quelle che definiscono una relazione di ordine. Sono quelle che utilizziamo non solo per i numeri interi, o razionali o reali, ma nella nostra vita. Le prime due sono, rispettivamente, le proprietà riflessiva e transitiva. Esprimono verità incontestabili.

Esempio

Ordinamento in base ai quattrini.
#x £ #y se x non ha più soldi di y.

1) Non ho più soldi di quanti ne ho (Proprietà riflessiva)
C'è da rifletterci davvero!

2) Non ho più soldi di B, B non ha più soldi di G, dunque io non ho più soldi di G.
Ovvio!

3) Se io non ho più soldi di Pippo e Pippo non ha più soldi di me, allora io e Pippo abbiamo gli stessi soldi.

Per ora conosciamo questi numeri cardinali:

I cardinali finiti, che identifichiamo con i numeri interi 0, 1, 2, 3, ...
Un cardinale infinito, À0, che è la cardinalità del numerabile.

Salv. E così dal vostro ingegnoso discorso si conclude, gli attributi di maggiore minore o eguale non aver luogo non solamente tra gl'infiniti, ma né anco tra gl'infiniti e i finiti.

Teorema
Dato un qualunque n in N, n < À₀
Dim. Per la Definizione 6, dobbiamo far vedere che
(1) n £ À₀
(2) non è vero che À₀ £ n.
Per provare la (1) consideriamo l'insieme A = {1, 2, ... , n}. Ovviamente #A = n. La funzione di A in N che manda i in i è una iniezione.
Proviamo ora la (2).
Sia f una qualsiasi funzione tra N e A. Allora le immagini f(1), f(2), ..., f(n+1) non possono esere tutte distinte, e la f non può essere una iniezione.

scoprì che esistono altri livelli di infinito, cardinali più grandi di À₀.

Diciamo c la cardinalità dell'insieme R dei numeri reali, ovvero c = #R.
c viene detta cardinalità del continuo

Vogliamo dimostrre che:

7 - Lemma
Se A è contenuto in B, allora #A £ #B
Dim. Conseguenza immediata della Definizione 4.

Sia I l'intervallo formato dai numeri reali compresi tra 0 e 1. Per il Lemma 7 si ha subito:

8 - Lemma
#I £ c

9 - Lemma
À₀ £ #I
Dim. Se poniamo f(n) = 1/n, f è chiaramente una funzione iniettiva di dominio N e codominio I. Dalla Definizione 4, e dal fatto che #N = À₀ segue che À₀ £ #I.

10 - Teorema (Cantor, 1874)
À₀ < c
Dim. Dal Lemma 9 sapiamo già che À₀ £ #I.
In base alla Definizione 6 se proviamo che non esiste alcuna iniezione tra I e N avremo

À₀ < #I e la tesi seguirà dal Lemma 8.
Ricordiamo ora la Proposizione 3:
Esiste una iniezione f: A ® B se e solo se esiste una suriezione g: B ® A.
Dunque non esiste alcuna iniezione tra I e N se e solo se non esiste alcuna suriezione tra N e I.
Avremo allora provato la tesi se facciamo vedere che assegnata una qualunque funzione f tra N e I, f non è suriettiva.
Gli elementi di I sono numeri reali compresi tra 0 e 1. Pertanto se a appartiene a I, ha una espressione del tipo:
a = 0,a₁a₂a₃a₄...., dove gli a_k sostituiscono la successione delle cifre decimali di a, e sono interi compresi tra 0 e 9.
Diciamo a₁ prima cifra di a, a₂ seconda cifra, e così via.
Data la funzione f, le immagini degli elementi di N mediante f sono:
f(1), f(2), f(3), ... , f(n), ...
Costruiamo un numero reale d appartenente a I con la regola seguente:

d = 0,d1d2d3d4....
Per ogni k dk è una cifra diversa dalla k-esima cifra di f(k).

E' facile ora dimostrare che d non è immagine di alcun elemento di N.
Infatti, dato un qualsiasi n in N, f(n) differisce da d almeno nella n-esima cifra.

L'insieme dei numeri reali non è numerabile!

Si osservi, per contrasto, che:

11 - Teorema
L'insieme S formato da tutte le stringhe finite binarie è numerabile.
Dim.
Lo proviamo elencandole.
La cosa è molto semplice: elenchiamo prima le sequenze di lunghezza 1, poi quelle di lunghezza 2, e così via.
Ci sono 2 sequenze di lunghezza 1: 0 ed 1; 4 di lunghezza 2: 00, 01, 10, 11; 8 di lunghezza 3…

La lista appare così:

1. 0


2. 1
3. 00


4. 01


5. 10


6. 11
7. 000


8. 001


9. 010


10. 011


11. 100


12. ......

  ...

   k. .......

La corrispondenza che associa ai numeri delle righe, scritti a sinistra, le relative stringhe binarie, è biunivoca.

12 - Corollario
Esistono numeri reali ineffabili.
Dim.
Non ci sono abbastanza parole per descrivere ogni numero reale.
Tecnicamente: tra l'insieme S e l'insieme R non esistono suriezioni.
[Ho trattato brevemente dei risvolti etici di questo corollario in una conferenza del 2000 : L'etica delle logiche]

13 - Esempi

Sia V un insieme finito di simboli.

1) L'insieme di tutte le sequenze finite di elementi di V è numerabile.
2) L'insieme di tutte le successioni di elementi di V ha cardinalità c.
3) La famiglia dei sottoinsiemi finiti di N è numerabile.
4) La famiglia di tutti i sottoinsiemi di N ha cardinalità c.
5) L'insieme C dei numeri complessi ha cardinalità c.

Diciamo numero algebrico un numero complesso che è radice di un polinomio (non nullo) con coefficienti razionali.
Diciamo numero trascendente un numero complesso che non è radice di alcun polinomio (non nullo) con coefficienti razionali.
I famosi numeri e e p sono trascendenti.

6) L'insieme dei numeri algebrici è numerabile.
7) L'insieme dei numeri trascendenti ha cardinalità c.
8) L'insieme dei numeri razionali è numerabile.
9) L'insieme dei numeri irrazionali ha cardinalità c.

Cantor dimostrò che esistono infiniti cardinali più che numerabili. La sua dimostrazione è costruttiva, Cantor fa vedere come, dato un cardinale a, si fabbrica un cardinale strettamente più grande di a.

La dimostrazione di questo fatto stupefacente è semplice, geniale e (non sembri un gioco di parole) infinitamente potente.

Serve prima una definizione

14 - Definizione

Dato un insieme X, diciamo insieme delle parti di X la famiglia di tutti i suoi sottoinsiemi. L'insieme delle parti di X viene denotato con P(X).

15 - Osservazioni
1) P({1, 2}) = {Æ, {1}, {2}, {1, 2}}. Il simbolo Æ denota l'insieme vuoto.
2) Se #X = n allora #P(X) = 2ⁿ.
Per questo motivo P(X) viene anche detto insieme potenza di X.

16 - Teorema (Cantor)

Per ogni insieme X, #X < #P(X)

Dimostrazione
La funzione tra X e P(X) che manda x in {x} è iniettiva. Pertanto #X £ #P(X).
Per provare la diseguaglianza stretta dobbiamo dimostrare che non esiste alcuna suriezione tra X e P(X).
Facciamo la dimostrazione per assurdo.
Sia g una funzione suriettiva tra X e P(X). Possiamo ripartire X nella unione di due sottoinsiemi disgiunti:
   A = {x tali che x appartiene a g(x)}.
   B = {x tali che x non appartiene a g(x)}.
Poiché g è suriettiva, esiste un y in X tale che g(y) = B.
Questo y deve stare in A o in B.
Se y sta in A, allora y appartiene a g(y), per definizione di A. Poiché g(y) = B, y appartiene a B. Ma questo non può essere, perché la intersezione di A con B è vuota.
Se y sta in B, allora y non appartiene a g(y), per definizione di B. Ma questo è contradditorio perché g(y) = B.
Siamo all'assurdo: si deve concludere che non esiste alcuna suriezione tra X e P(X).

17 - Esempio

La tecnica è questa, dato a₀, si prende X₀ tale che #X₀ = a₀, e si costruiscono
X₁ = P(X₀)
X₂ = P(X₁)
....
X_n+1 = P(X_n)
....

Se si pone a_i = #X_i allora la sequenza a₀, a₁, a₂, ... , a_n, ...
è formata da numeri cardinali, ove ognuno è strettamente più grande del precedente.

1) Se si parte con a₀ = 0, abbiamo X₀ = Æ e
X₁ = P(X₀) = P(Æ) = {Æ}
X₂ = P(X₁) = P({Æ}) = {Æ, {Æ}}
X₃ = P(X₂) = P({Æ, {Æ}}) = {Æ, {Æ}, {{Æ}}, {Æ, {Æ}}}
....
X_n+1 = P(X_n)
....

e questa è la successione degli a_i
a₁ = 1
a₂ = 2
a₃ = 4
....
a_n+1 = 2ⁿ
....

2) 1) Se si parte con w₀ = À₀, abbiamo X₀ = N e
X₁ = P(X₀) = P(N)
X₂ = P(X₁) = P(P(N))
X₃ = P(X₂) = P(P(P(N)))
....
X_n+1 = P(X_n)
....

e questa è la successione degli w_i
w₁ = #P(N) = #R = c [vedi 13 4)]
w₂ = #P(P(N)) = #P(R)
w₃ = #P(P(P(N))) = #P(P(R))
....

Per costruzione si ha: w₀ < w₁ < w₂ < w_n... < ....
Una successione di infiniti sempre più grandi! Il cardinale w₂ è la cardinalità dell'insieme di tutte le funzioni di R in se stesso! Grandino vero? Eppure tutti i ragazzi delle medie superiori lavorano in questo ambiente!

Chi è À₁?
À₀ è il più piccolo cardinale infinito: se a < À₀ allora a è la cardinalità di un insieme finito.
À₁ è definito come il cardinale che lo segue, ovvero il livello successivo di infinito.
À₁ è il il più piccolo cardinale non numerabile.

Domanda sulla identità di À₁
E' c il più piccolo cardinale non numerabile?
Equivalentemente: è vero che À₁ = c?

all'inizio del 1900.

Si trattava di una domanda destinata a rimanere senza risposta, nell'ambito della teoria standard degli insiemi.

Eppure questa domanda ha una formulazione equivalente estremamente concreta:

Domanda equivalente Esistono sottoinsiemi non numerabili di R la cui cardinalità sia strettamente minore di c?

dimostrò che la cosiddetta Ipotesi del Continuo CH

Ne consegue che CH è indipendente dagli assiomi della teoria standard degli insiemi. Si potrebbe chiamare "Postulato del continuo". Si può sviluppare una teoria degli insiemi in cui si postula che esistano cardinalità intermedie tra quella di N e quella di R, e una teoria degli insiemi nella quale questa esistenza viene negata.

A noi la scelta!

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

11 Settembre 2005

1. Grafi

Poiché molti problemi difficili e interessanti riguardano i grafi, premettiamo una breve introduzione al loro studio.

Un grafo G = (V,E) è costituito da un insieme V di vertici e da un insieme E di archi.

Terminologia essenziale:

1. Due vertici si dicono adiacenti se c'è un arco che li connette.
2. Un grafo si dice semplice se non possiede cappi (ovvero archi che congiungono un vertice a se stesso) e non ha archi multipli (cioè due vertici adiacenti sono connessi da un solo arco).
3. Il grado di un vertice v, deg(v), è il numero di archi incidenti in v.
4. Un grafo si dice k-regolare se, per ogni suo vertice v, deg(v) = k.
5. Un grafo si dice completo (si dice anche clique o cricca) se due vertici qualsiasi sono adiacenti.
6. Un percorso di lunghezza n è una sequenza di n+1 vertici v_j (con j = 1, 2, ..., n+1), non necessariamente distinti, tali che, per ogni j minore di n+1, v_j e v_j+1 sono adiacenti. Se il primo e l'ultimo vertice di un percorso coincidono, il percorso si dice chiuso. Se i vertici sono tutti distinti il percorso si chiama cammino. Un circuito (o ciclo) di lunghezza n è una sequenza di n vertici distinti v₁, v₂, ... , v_n dove v₁ è adiacente a v₂, v₂ è adiacente a v₃, ... , v_n è adiacente a v₁.
7. Due vertici si dicono connessi se esiste un cammino che li congiunge. Un grafo G è connesso se ogni coppia di vertici di G è connessa.
8. Un grafo si dice planare se si può disegnare su un piano in modo tale che i suoi archi si incontrino solo nei vertici.
9. Un grafo si dice k-colorabile se i suoi vertici possono essere colorati con k colori in modo tale che due vertici adiacenti abbiano sempre colore diverso.
10. Diciamo percorso euleriano un percorso chiuso che attraversa ogni lato di G esattamente una volta. Se un grafo possiede un percorso euleriano si dice grafo euleriano.
11. Diciamo circuito hamiltoniano un circuito che visita ogni vertice di G esattamente una volta. Se un grafo possiede un circuito hamiltoniano si dice grafo hamiltoniano.

Figura 1

G ha 5 vertici e 8 archi. Sono adiacenti le coppie di vertici (A, B), (B, C), (C, D), (D, E), (E,A), (A, D), (A, C), (B, E).
G è semplice.
I gradi sono:

dag(A) = 4
deg(B) = deg(C) = deg(D) = deg(E) = 3

Figura 2

Come si vede dalla Figura 3, G è 3-colorabile.

Figura 3

G non è euleriano.
G è hamiltoniano, un circuito hamiltoniano evidente è A - B - C - D - E - A.

Se completiamo G otteniamo la cricca H di Figura 4.

Figura 4

Naturalmente H è ancora hamiltoniano. H è anche euleriano, un percorso chiuso è
A - B -C - E - B - D - C - A - D - E - A

E' spontaneo chiedersi il motivo per cui i grafi euleriani hanno questo nome. La storia risale al 1736. In quel tempo Eulero (il grande matematico Leonhard Euler (1707 - 1783)) viveva a Koenigsberg (l'attuale Kaliningrad), città costruita su due isole collegate da sette ponti (distrutti durante la II guerra mondiale). Eulero desiderava fare una passeggiata che, partendo da casa, gli facesse attraversare ogni ponte una volta sola e lo riportasse al punto di partenza. Questo però non gli riusciva mai. Si mise a riflettere, e disegnò un grafo simile a quello di Figura 5:

Figura 5

I sette archi rappresentano i sette ponti, mentre i quattro vertici sono le zone della città da essi collegate. Eulero capì subito che fare un percorso come lui desiderava su di un grafo è possibile solo se il grado di ogni vertice è pari. Quindi la sua passeggiata era impossibile!

Nel 1873 Carl Hierholzer provò che la condizione trovata da Eulero non è solo necessaria, ma anche sufficiente. Sussiste perciò il seguente notevole teorema, che caratterizza in modo semplicissimo i grafi Euleriani:

Teorema 1

Un grafo connesso G è euleriano se e solo se ogni vertice di G ha grado pari.

Figura 6

Nella sottostante Figura 7 si vedono i grafi dei solidi platonici. Da sinistra a destra e dall'alto in basso si trovano il tetraedro, il cubo (esaedro), l'ottaedro, il dodecadro e l'icosaedro.

Figura 7

Sono tutti planari e k-regolari, con k = 3 per il tetraedro, il cubo e il dodecaedro, k = 4 per l'ottaedro e k = 5 per l'icosaedro.

Essi sono tutti hamiltoniani, ma soltanto l'ottaedro è euleriano (per il Teorema 1).

Non esiste una caratterizzazione semplice dei grafi hamiltoniani, come invece accade per quelli euleriani. Esistono condizioni necessarie, molto lontane dall'essere sufficienti, del tipo

Se un grafo è hamiltoniano allora è connesso.
Se un grafo è hamiltoniano allora ogni suo vertice v di grado 2 è tale che
qualsiasi circuto hamiltoniano contiene i due archi incidenti in v.

Teorema 2 (Dirac, 1952)

Sia G un grafo semplice con n > 2 vertici. Se per ogni vertice u di G si ha

deg(u) ³ n/2
allora G è hamiltoniano.

Teorema 3 (Ore, 1960)

Sia G un grafo semplice con n > 2 vertici. Se per ogni coppia u, v di vertici non adiacenti si ha

deg(u) + deg(v) ³ n
allora G è hamiltoniano.

Figura 8

osserviamo che deg(u) = 2 è minore in senso stretto di n/2, poiché n vale 5. Quindi non si applica il Teorema 2. E' possibile invece utilizzare la condizione di Ore, in quanto la somma dei gradi di due vertici non adiacenti è sempre ³ 5.

Purtroppo nel mondo reale per essere un grafo hamiltoniano non occorre avere così tanti archi! Si osservi che le condizioni di Dirac o di Ore sono false per alcuni dei solidi platonici, malgrado essi siano tutti hamiltoniani.

Il fatto che manchi una caratterizzazione semplice dei grafi hamiltoniani ha radici profonde, come si capirà dal seguito dell'articolo.

2. La classe dei problemi P

Possiamo far risalire le origini della moderna teoria della complessità computazionale al 1936, quando Turing ideò la macchina che porta il suo nome, prototipo ideale del nostro computer. In quegli anni Turing, Church e altri affrontarono il problema alle radici, fornendo una definizione esatta di computabilità. Essi provarono che esistono limiti invalicabili: ci sono funzioni perfettamente definite ma non computabili (si veda Alan Turing e i suoi alacri castori.), esistono problemi indecidibili, domande alle quali nessuno saprà mai rispondere sì o no (si veda Indecidibilità del problema dell'arresto). Nel 1965 Hartmanis and Stearns, nell'articolo "On the Computational Complexity of Algorithms", cercarono per la prima volta di quantificare la complessità computazionale in tempo e in spazio, utilizzando come modello di calcolo una macchina di Turing. Supponiamo di inserire nella macchina M la codifica di un numero intero N, e che M sia programmata per decidere se N è primo o meno. Dopo T passi la macchina si ferma e risponde. T è la misura della complessità in tempo. Il numero V delle celle diverse sulle quali si è fermata la testina di M misura la complessità in spazio; oggi diremmo che V è la quantità di memoria necessaria al calcolo.

Ci occuperemo qui soltanto della complessità in tempo. Il nostro modello di calcolo è semplicemente il computer che abbiamo sulla scrivania.

Prima di partire dobbiamo richiamare un paio di cose.
Denotiamo con N l'insieme dei numeri naturali {0, 1, 2, 3, ... }.

Definizione 1
Diciamo che una funzione f : N ® N è polinomiale se esiste k tale che,
da un certo n in poi, si ha sempre f(n) £ nk.

Definizione 2
Diciamo che una funzione f : N ® N è esponenziale se esiste a > 1 tale che,
da un certo n in poi, si ha sempre f(n) ³ an.

Poniamo g(n) = n5 e h(n) = 1.333n
Facciamo assumere a n gli 11 valori
n = 2, 12, 22, 32, 42, 52, 62, 72, 82, 92, 102
Crescita polinomiale con grado uguale a 5:
g(n) = 32, 248832, 5153632, 33554432, 130691232, 380204032, 916132832, 1934917632, 3707398432, 6590815232, 11040808032
Crescita esponenziale con base uguale a 1.333:
h(n) = 1.776, 31.474, 557.523, 9875.629, 174930.797, 3098616.074, 54886970.905, 972233894.960,17221550596.025, 305051908258.412, 5403501050227.986
Osserviamo l'andamento del rapporto h(n)/g(n):
h(n)/g(n) = 0.0555278, 0.00012649, 0.000108181, 0.000294317, 0.0013385, 0.00814988, 0.0599116, 0.502468, 4.64518, 46.2844, 489.412
Per n = 102 h(n) è già quasi 500 volte più grande do g(n).
Per n = 200 il rapporto h(n)/g(n) è ben 2.88 x 1013.

Convenzioni:
Il termine  "intero" si riferirà sempre ad un intero positivo, se non diversamente specificato.
Tutti i grafi considerati nel seguito si intendono semplici e connessi.
Se A è un insieme finito di numeri, S(A) denota la somma degli elementi di A.

Un problema decisionale è composto da una infinità di istanze, ognuna della quali è determinata da una particolare scelta dei dati. Per ogni istanza c'è una domanda che ha una sola risposta: sì o no.

Vediamo alcuni esempi:

1. Nome: Problema del Riconoscimento della Potenza Perfetta
   Istanza generica:
   
   • Dati: un intero N
     
   • Domanda: Esistono due interi m e k maggiori di 1 tali che N = m^k?
   
   

2. Nome: Problema del Riconoscimento dei Numeri Primi
   Istanza generica:
   
   • Dati: un intero N
     
   • Domanda: N è primo?
   
   

3. Nome: Problema del Grafo Euleriano
   Istanza generica:
   
   • Dati: un grafo G con n vertici
     
   • Domanda: G è un grafo euleriano?
   
   

4. Nome: Problema dello Zaino
   Istanza generica:
   
   • Dati: un insieme A contenente n interi ed un intero K
     
   • Domanda: A contiene un sottoinsieme B tale che S(B) = K?
   
   

5. Nome: Problema della Partizione
   Istanza generica:
   
   • Dati: un insieme X contenente n interi
     
   • Domanda: Esiste una partizione di X in due sottoinsiemi A e B tali che |S(A) - S(B)| £ 1?
   
   

6. Nome: Problema della Equazione Diofantina Quadratica
   Istanza generica:
   
   • Dati: tre interi A, B e C
     
   • Domanda: Esistono due interi x e y tali che Ax² + By = C?
   
   

7. Nome: Problema della Congruenza Quadratica Limitata
   Istanza generica:
   
   • Dati: tre interi A, B e C
     
   • Domanda: Esiste un intero x £ C tale che il resto della divisione di x² per B sia A?
     (Equivelentemente, esiste un intero x £ C tale che x² = A (mod B)?)
   
   

8. Nome: Problema del Grafo Hamiltoniano
   Istanza generica:
   
   • Dati: un grafo G con n vertici
     
   • Domanda: G è un grafo hamiltoniano?
   
   

9. Nome: Restrizione del Problema del Grafo Hamiltoniano
   Istanza generica:
   
   • Dati: un grafo 3-regolare planare G con n vertici
     
   • Domanda: G è un grafo hamiltoniano?
   
   

10. Nome: Problema del Commesso Viaggiatore
    Istanza generica:
    
    • Dati: un grafo G con n vertici, l'assegnazione di un costo (un numero positivo) ad ogni arco, ed un numero B (il limite di spesa)
      
    • Domanda: Esiste in G un percorso hamiltoniano tale che la somma dei costi degli archi che fanno parte del percorso non superi B?
    
    

11. Nome: Problema della 3-Colorazione
    Istanza generica:
    
    • Dati: un grafo G con n vertici
      
    • Domanda: E' possibile colorare G con 3 colori?
    
    

Si noti che esiste sempre almeno un algoritmo che risponde a questi problemi decisionali: l'algoritmo di forza bruta. Esso esplora tutto lo spazio di ricerca (che è finito) constatando banalmente se una soluzione esiste o meno.
Nel caso di 2 lo spazio di ricerca è costituito dagli interi dispari V minori o uguali della radice quadrata di N; l'algoritmo divide N per V. La grandezza dello spazio di ricerca, che è proporzionale alla radice quadrata di N, risulta essere esponenziale nel peso dei dati, cioé nel numero dei bit di N.
Allo stesso modo per risolvere il problema 4 con l'algoritmo "stupido" bisogna esplorare lo spazio di tutti i sottoinsiemi B di A, calcolando ogni volta S(B). Però ci sono 2ⁿ sottoinsiemi di A, e quindi la grandezza dello spazio di ricerca è ancora esponenziale nel peso dei dati, che qui è n.
Questo vale per tutti gli 11 problemi elencati e, in generale, per tutti i problemi interessanti.

Possiamo ora definire la classe dei problemi P.

Definizione 3
Un problema decisionale Q appartiene alla classe P se esiste un algoritmo che
per ogni istanza I di Q risponde in un tempo £ dk, 
dove d è il peso della istanza I, e k è un intero fissato indipendente da I. 

Diamo un'occhiata ai nostri problemi. L'unico che si rivela immediatamente polinomiale è il 3. Per il Teorema 1, data una istanza di peso n, cioè un grafo G con n vertici, per rispondere è sufficiente vedere se il grado di ogni vertice è pari.

Per risolvere il problema 1 sono noti da tempo algoritmi polinomiali assai efficaci.

Quanto al 2, il problema di riconoscere se un intero N è primo, è stato dimostrato essere in P soltanto nel 2002. Si tratta di un risultato epocale, dovuto a tre matematici indiani: Agrawal, Kayal e Saxena.

Non si sa se i rimanenti otto problemi siano o meno in P. Per essi non è noto alcun algoritmo polinomiale. Come si capirà dal seguito, è molto improbabile che tali algoritmi esistano, e sarebbe di straordinaria importanza trovarne anche uno solo.

E' possibile definire una gerarchia di difficoltà tra i problemi? Intuitivamente potremmo dire che un problema Q è più facile di Q' se chiunque sia in grado di risolvere Q' è anche capace di risolvere Q.

Formalizziamo l'intuizione. La chiave sta nel concetto di riduzione di un problema ad un altro:

Definizione 4
Diciamo che il problema Q è riducibile al problema Q', e scriviamo Q ® Q', se
1) esiste una funzione f calcolabile in tempo polinomiale che trasforma
   ogni istanza I di Q in una istanza I' = f(I) di Q'.
2) f(I) ha risposta sì se e solo se I ha risposta sì.

E' intuibile che il problema 8 (del Grafo Hamiltoniano) sia riducibile al problema 10 (quello del Commesso Viaggiatore), in quanto il secondo richiede comunque che si provi che il grafo è hamiltoniano. Ed è vero, come si può dimostrare rigorosamente.

Quello che è sorprendente è che ogni problema dal 4 all'11 può essere ridotto ad un altro problema qualsiasi, nello stesso intervallo.

Si noti che la relazione ® è evidentemente riflessiva:

Q ® Q

Q ® Q' e Q' ® Q'' implica Q ® Q''

Definizione 5
Diciamo che i problemi Q e R sono equivalenti se
Q ® R  e  R ® Q 

Da quanto detto sopra segue che i problemi 4 - 11 sono tutti equivalenti: se si riesce a risolvere uno di essi in tempo polinomiale, si riesce per tutti gli altri.

Incredibile, vero?

Inoltre, e non è affatto ovvio, ognuno dei problemi 1 - 3 può essere ridotto ad uno qualsiasi dei problemi 4 -11, mentre non è nota, e probabilmente non esiste, alcuna riduzione in senso contrario.

Torneremo su questo nel paragrafo 6.

3. La classe dei problemi NP

Per i problemi più importanti che vengono dalla teoria dei numeri, dalla combinatorica e dalle applicazioni concrete non sono noti algoritmi che li risolvano in tempo polinomiale. Non si sa dunque, proprio come per i problemi 4 - 11 del paragrafo 2, se essi stiano o meno nella classe P.

Si è pensato dunque di introdurre una nuova classe, quella dei problemi che sono risolubili in tempo polinomiale da una macchina di Turing non-deteministica. Questa classe viene chiamata NP. Si noti bene che la N (non) non si riferisce alla P (polinomiale) ma al termine "deterministico".

Si ricorderà che una macchina di Turing è una macchina che, al passaggio del tempo da t a t+1, passa da uno stato s(t) ad uno stato s(t+1), completamente determinato da s(t) e dall'input al tempo t. Una macchina di Turing non deterministica è una macchina che può assumere simultaneamente più stati:

s(t+1) non è uno stato ma un insieme di stati.

GOTO Label

possiede anche questa:

GOTO {Label₁, Label₂, Label₃, ... Label_k}, con k finito ma non limitato

Un altro modo per vedere una macchina di Turing non deterministica M è questo:

M è una macchina capace di parallelismo illimitato

Consideriamo il Problema dello Zaino con n = 100, ed una certa somma assegnata K. Il programma di forza bruta esaminerà, in un certo ordine, i 2¹⁰⁰ sottoinsiemi B di A, calcolando per ognuno di essi la somma S(B), per vedere se è uguale a K. Se esiste un solo sottoinsieme la cui somma è K e se si trova casualmente al fondo della lista, il programma dovrà eseguire 2¹⁰⁰ somme, e non lo vedremo mai terminare. Invece un programma non deterministico può creare 2¹⁰⁰ cloni di se stesso. Ognuna di queste copie esegue una somma sola!

Il tempo di esecuzione si è ora ridotto al tempo necessario per la verifica del fatto che un elemento dello spazio di ricerca sia una soluzione.

Ora chiediamoci, come ottenere veramente la risposta?

Tutti i cloni hanno questa semplicissima forma (come programmi):

Input : Un insieme B di interi e una somma desiderata K.
Output : "Successo", se S(B) = K
              "Fallimento", altrimenti.

Prendiamo un clone, Pippo, a caso (Pippo potrebbe, del tutto equivalentemente, essere il primo clone che risponde). Se Pippo risponde "Successo", la risposta è sì. Nel nostro caso, quello (ricordiamolo) del problema dello zaino, la risposta è chiara e forte : esiste un sottoinsieme B di A che ha somma S(B) = K (e Pippo può anche dirci qual è). Se invece la risposta di Pippo è "Fallimento", non abbiamo ottenuto nessuna informazione. Infatti per altri sottoinsiemi B, ove sono posizionati altri cloni, si potrebbe avere risposta "Successo". La differenza è sostanziale: basta che uno che risponda "Successo" per poter dire sì, mentre è necessario che tutti rispondano "Fallimento" per essere certi della risposta no.

Dopo questa chiacchierata informale sulla classe NP, diamo una definizione esatta di essa, anche se privata di alcuni tecnicismi che la appesantirebbero:

Definizione 6
Diciamo che un problema decisionale Q appartiene alla classe NP
se ogni istanza sì di Q può essere verificata in tempo polinomiale.

(N.B. Per istanza sì del problema  Q intendiamo, ovviamente,
una istanza del problema che ha risposta sì.)

La classe P è contenuta nella classe NP

Quasi sempre è facile provare che un problema Q appartiene alla classe NP. Dobbiamo dimostrare che ogni istanza sì di Q possiede un certificato controllabile in tempo polinomiale. Per i problemi 4 - 11 del paragrafo 2 è semplicissimo. Vediamo insieme il numero 6:

Problema della Equazione Diofantina Quadratica.
Istanza sì : A = 123456789, B = 987654321, C = 449506169442
Certificato: x = 55, y = 77

Non sempre però è facile trovare quale certificato possa essere al tempo stesso succinto (cioé verificabile in tempo polinomiale) e convincente. Non è facile invertarsi un certificato utile.

Sembra strano? Riposiamoci un poco con il racconto che segue. (Salta il racconto)

4. L' Oracolo dei numeri primi

Tanto tempo fa in una valle ubertosa e salubre viveva un popolo pacifico e laborioso, composto da ben 144.001 famiglie. Regnava la pace, non c'erano poveri (e nemmeno ricchi), le malattie erano sconosciute. Il clima era perfetto. Canali ricolmi di acqua irrigavano i campi. Fiumi tranquilli e allegri ruscelli fecondavano e rallegravano quelle terre benedette. A seconda delle stagioni i pascoli abbondavano di verde, i prati si rivestivano di greggi, le valli si coprivano di un manto di frumento, o si udivano le liete grida di gioia dei vendemmiatori, provenienti dai colli fitti di vigne. Ovunque cantavano uccelli variopinti, vi erano fiori, frutti succosi, boschi e foreste immense ove si ergevano orgogliosi grandi e maestosi alberi. Il tutto era di proprietà di un ben noto Oracolo, persona assai potente ma mite. Sapiente come nessun altro, ma modesto e gentile.

La gente era allegra, amava giocare e chiacchierare. D'inverno si correva con gli slittini sul lago ghiacciato, e in ogni stagione si passeggiava tra incantevoli giardini. Particolarmente amato era il Giardino dei Numeri, sempre pieno di pubblico ammirato. I suoi viali erano talmente lunghi che nessuno ne aveva mai visto la fine. Tutti camminavano a testa in su per gustare la vista dei Numeri che ornavano le chiome delle piante. I Numeri erano colorati di mille sfumature diverse, avevano forme preziose, a volte incredibilmente complesse, ma sempre belle e sorprendenti. Gli abitanti della valle li distinguevano benissimo uno dall'altro, anche per i deliziosi suoni che emettevano quando venivano fatti vibrare da una sottile brezza che spirava sempre in quel giardino, e nessuno sapeva da dove venisse. Tra tutti i Numeri spiccavano i Primi. Il loro splendore lasciava senza respiro, e una persona diceva all'altra, sottovoce, quasi intimidita, frasi come questa: "Guarda caro come è bello quel Primo lassù, non l'avevo ancora visto! Somiglia tanto a quello che abbiamo scoperto ieri, ti ricordi? Quello di Sophie Germain!" Salendo sugli alberi, i Numeri che stavano sui rami bassi si potevano raggiungere e toccare. Erano molto gradevoli al tatto. Alcuni a sprimacciarli ben bene si sentiva subito che erano composti, mentre altri eran fatti tutti d'un pezzo.

Come si diceva il popolo era bonaccione ed innocuo. Nessuno si sarebbe sognato di far del male ad un altro o di rubare qualcosa, o anche solo di essere invidioso, maldicente, bugiardo o di comportarsi da meleducato. Qundi non c'era bisogno di leggi. Non vivevano lì uomini politici, giudici, avvocati, poliziotti o militari. Veramente una legge c'era, una sola. Più che una legge era un favore, che aveva chiesto l'Oracolo. E chi si sarebbe sentito di negarglielo, un piccolo favore, ad una persona tanto buona e generosa. Il favore era questo: "Per cortesia, non portate via i Numeri! Lasciateli tranquilli dove stanno, sugli alberi!"

E c'erano anche dei buoni motivi, che l'Oracolo aveva spiegato a tutti. Se levate i Numeri dalle piante, avvizziscono, perdono i colori, non suonano più e diventan pure viscidi, che fa schifo toccarli! E poi non c'è ragione di portarseli a casa. Sono sempre lì, e il Giardino è sempre aperto. Potete sempre guardarli. Ma se uno si porta a casa un numero, poi gli altri non possono più vederlo! Non è una bella cosa!

E tutti concordavano, perché i motivi erano sensatissimi, ed il piacere chiesto con tanto garbo. Però... purtroppo non erano proprio tutti.

La famiglia degli Adami non aveva saputo resistere alla tentazione di portarsi qualche bel Primo a casa. Pochi pochi all'inzio, ma poi la passione li aveva travolti, e ne avevano presi molti. Naturalmente l'Oracolo, che conosceva i Numeri uno per uno (non c'è da stupirsi, chiamava per nome anche le stelle del cielo!) se n'era accorto subito. Più volte si era recato a casa degli Adami e aveva detto loro: "Ragazzi miei, perché fate così? Rimettete i Primi al loro posto, altrimenti l'armonia si guasta, senza la loro musica. Ci sono nei viali sequenze segrete, che vi ho messo io, e un giorno le scoprirete! Così si guasta tutto, non mi tornano più i conti! Fatemi un piacere, riportateli dove li avete presi. Torneranno subito belli come prima!"

Gli Adami rispondevano sì, sì, ma, ormai succubi del loro vizio (il primo in quella terra benedetta!), seguitavano a rubare.

E la gente cominciava a lamentarsi con l'Oracolo. Uno, quasi piangendo, diceva: "Prima c'erano 168 Primi prima del Numero 1000, ora ce ne sono soltanto 122! Che cosa è successo? Li conoscevo tutti, mi piacevano tanto! E ora?" Un altro, quasi adirato, alzava la voce e gridava: "Dove è finito il 134757431? Era anche della stirpe dei Palindromi! E' una vergogna ... che mondo!"

Allora l'Oracolo andò dagli Adami e disse loro:

"Per causa vostra in questo popolo felice stanno nascendo tristezza ed ira. Questo non deve accadere, ed io non lo permetterò, Se non riportate subito i Primi al loro posto, sarò costretto a mandarvi via."

Gli Adami si erano insuperbiti, perché erano i soli a fare quello che facevano, e si sentivano più intelligenti di tutti. Così risposero:

"Va bene, ce ne andremo, il mondo è grande. E, fuori dalla valle, potremo raccogliere tuttti i primi che vogliamo e tenerceli!"

L'Oracolo era tanto benevolo che volle ancora consigliarli:

"Guardate che fuori di qui i Numeri non stanno mica sopra gli alberi! Avrete a che fare soltanto con i nomi dei numeri. Questi non si toccano, non hanno colori, non risuonano! Vi sembreranno tutti uguali, e non saprete distinguere i nomi dei Primi dagli altri!"

Ma gli Adami non volevano capire, non ragionavano. Orgogliosamente i poveretti esclamarono:

"Se ci riesci tu, a distinguerli tanto bene, riusciremo certamente anche noi!"

Presero tutto, tranne ovviamente i Primi rubati, e se ne andarono sbattendo la porta.

L'Oracolo in un primo momento divenne malinconico. In seguito si convinse di avere agito per il meglio. I Primi erano di nuovo tutti nei luoghi precisi loro assegnati, e il popolo della valle gioiva come sempre guardandoli e chiedendosi curioso "Dove sarà il prossimo Primo, come sarà fatto?" Alla fine l'Oracolo si consolò della partenza degli Adami, e si diceva "In fondo sono rimaste 144.000 famiglie! E' brava gente, che starà con me per sempre!"

La stirpe degli Adami si accorse ben presto che l'Oracolo aveva ragione. I numeri, lontano dalla valle, sembravano tutti uguali, e riconoscere i primi era estremamente faticoso. Anche con il crivello di Eratostene ci voleva troppo tempo. Un giorno uno (quasi) di loro, assai meno superbo, di nome Mino, si rivolse all'Oracolo dicendogli:

"Senti, so che sei vicino, anche se non ti vedo. So che mi stai ascoltando. Ho messo insieme parecchi Primi. Ma sono piccoli, hanno poche cifre! Me ne regaleresti uno grandino, diciamo di 20 cifre?"

Immediatamente l'Oracolo, che si aspettava la domanda, rispose:

"Eccolo caro, p = 79925742525202824779"

Felicissimo, con la sua scrittura lineare e minuta, Mino si segnò il nome. Cioè il numero, ... , insomma il nome del numero.

Dopo alcuni giorni Mino si rivolse ancora all'Oracolo:

"Come faccio a sapere che il numero che mi hai regalato è davvero primo?"

"Sapevo che me lo avresti chiesto" - sospirò l'Oracolo - "e mi verrebbe voglia di rispnderti che - a caval donato non si guarda in bocca! Ma non lo faccio, perché vedo quanto ci tieni. Caro Mino, io potrei convincerti, senza dubbio. Io so come fare. Ma sarebbe una costrizione, lontana dal mio modo di essere. So che siete gente dalla testa dura. Avete buona vista, ma tenete gli occhi chiusi. Perché non ci sia violenza, devi dirmi tu, come potrei convincerti."

"Vorrei un certificato", osò Mino.

L'Oracolo fece una pausa, e buttò lì, sornione: "Se vuoi, ti passo l'elenco dei resti delle divisioni di p per gli interi, da 2 a p-1, che lo precedono. Vedrai con i tuoi occhi che essi non sono mai zero!"

Mino inorridì. "Assurdo!" - gemette - "Tanto varrebbe verificarlo da solo, e con il metodo più stupido" - aggiunse con malcelato disprezzo.

Poi Mino addolcì la voce.:

"Oracolo sottile e penetrante, ho capito che benevolmente tu mi vuoi mettere alla prova. Ma non sono stupido come una bestia! Qui dove abito c'è ben poco da fare. E' un posto chiuso, senza luce e pieno di muri. Il vitto poi, ... è disgustoso. La mia sola gioia consiste nel cercare i numeri primi. In tutti questi anni ho dimostrato alcuni interessanti teoremi, e ho trovato anche certi metodi veloci di calcolo..."

La voce dell'Oracolo pareva sempre più lontana:

"Che cosa vuoi allora, quale certificato chiedi, dimmelo e te lo darò!"

Ormai Mino piangeva.

"Non lo so! Non lo so! Non lo so ... ancora!"

Passarono molti anni. Poi Mino chiamò ancora l'Oracolo, e gli disse che cosa desiderava. Precisò anche che per i primi fino a 10.000 non gli serviva alcun certificato, perché li aveva calcolati tutti, uno per uno, con grande cura, e li conosceva.

L'Oracolo ascoltò attentamente, e subito diede a Mino il certificato che Mino voleva, e Mino lo verificò e fu felice!

L'Oracolo pensò, tra sè e sè, che gli Adami erano testardi e duri di cuore, ma alcuni di loro si davano davvero un gran daffare! E concluse:

"Chissà, forse un giorno torneranno nella mia valle!"

5. Primi Certificati

Un'altra definizione (equivalente alla Definizione 6) della classe NP, che fa uso esplicito dei certificati, è la seguente:

Definizione 7
Diciamo che un problema decisionale Q appartiene alla classe NP
se esiste un Oracolo il quale, per ogni istanza sì di Q 
fornisce un certificato che può essere verificato in tempo polinomiale.

Consideriamo per esempio il:

Problema del Riconoscimento dei Numeri Composti

• Dati: un intero N
• Domanda: N è composto?

Se l'intero N è composto l'Oracolo fornisce un certificato contenente un divisore D di N. Per verificare dovremo soltanto dividere N per D.

Questo dimostra che

Teorema 4

Il Problema del Riconoscimento dei Numeri Composti appartiene a NP.

Nessuno riuscì in questa impresa fino al 1974, quando Vaughan R. Pratt ideò per la prima volta nella storia un Certificato di Primalità Verificabile in Tempo Polinomiale (CPVTP).

Il CPVTP si basa sul seguente teorema di Lucas:

Teorema 5

Supponiamo che D = {q₁, q₂, ..., q_m} sia l'insieme dei divisori primi di N-1.

N è primo se e solo se esiste un a tale che per ogni q in D valgono le:

1) a^N-1 = 1 (mod N)
2) a^(N-1)/q ¹ 1 (mod N)

(Ricordiamo che a = b (mod N) significa che N divide a-b. Equivalentemente b è il resto della divisione di a per N)

Esempio di applicazione del teorema di Lucas.

Sia dato N = 1297 = 64 + 1.

In questo caso la fattorizzazione di N - 1 è immediata:
N - 1 = 1296 = 64 = 24·34

Pertanto l'insieme dei divisori primi di N - 1 è:
D = {2, 3}

Scegliamo una base a, a = 10.

Per verificare la condizione 1) del teorema di Lucas, calcoliamo
101296 (mod 1297)
Si ottiene 1, OK.

Verifichiamo ora la condizione 2).
Poniamo q = 2:
101296/2 =  10648 (mod 1207)
Si ottiene 1296, OK.

Manca soltanto q = 3, calcoliamo:
101256/3 = 10432 (mod 1207)
Si ottiene 365, OK.

Concludiamo che, per il Teorema di Lucas, 1297 è primo.

Vediamo ora il Certificato di Pratt. Si tratta in realtà di un insieme di certificati.

Certificato di Pratt

Supponiamo di conoscere i primi fino ad un limite L. Dato N primo, l'oracolo deve solo certificare la primalità di N.

L'oracolo fornisce l'insieme D dei divisori primi di N - 1. L'oracolo fornisce un intero a che soddisfa le due condizioni del teorema di Lucas per ogni q in D.

La procedura è ricorsiva.

Per ogni primo q in D maggiore di L l'oracolo fornisce un certificato, sino a quando tutti i primi coinvolti sono minori di L

Esempio di certificazione di un primo con il metodo di Pratt
Supponiamo, per semplicità, di conoscere l'elenco dei primi fino a 10.000.

Sia dato il numero N = 79925742525202824779.

L'oracolo fornisce l'insieme dei divisori primi di N - 1:
D = {2, 11, 263, 53279, 259269950887}.
L'oracolo fornisce la base a = 2.

L'utente U, con divisioni successive, verifica che
N - 1 = 2·11·263·53279·259269950887
(N.B. Il fatto che tutti i primi appaiano con esponente 1 è del tutto fortuito)

U calcola:

2N-1 (mod N) = 1 
2(N-1)/2 (mod N) = 79925742525202824778
2(N-1)/11 (mod N) = 76721605684067720274
2(N-1)/263 (mod N) = 71522329290127897097
2(N-1)/53279 (mod N) = 26384095619722806544
2(N-1)/259269950887 (mod N) = 2959614048108645507

A questo punto U sa che se gli elementi di D sono davvero primi
allora, per il Teorema di Lucas, N è primo. Visto il suo elenco,
U sospetta di q4 = 53279 e di q5 = 259269950887.

L'oracolo fornisce un certificato per 53279.
Offre la fattorizzazione di 53278:
53278 = 2·17·1567
e una base che funziona, a = 2.

U verifica la fattorizzazione.
U calcola:
253278 (mod 53279) = 1
253278/2 (mod 53279) = 37052
253278/17 (mod 53279) = 31344
253278/1567 (mod 53279) = 5138

Poiché U sa che 2, 17 e 1567 sono primi, 53279 è certamente primo.

Ora l'oracolo fornisce un certificato per 259269950887.
Fattorizzazione di 259269950886:
259269950886 = 2·3·29·2441·610429
Una base che va bene, a = 3 (in questo caso 2 non funziona).

U verifica la fattorizzazione.
U calcola:
3259269950886 (mod 259269950887) = 1
3259269950886/2 (mod 259269950887) = 259269950886
3259269950886/3 (mod 259269950887) = 176218747612
3259269950886/29 (mod 259269950887) = 39029987097
3259269950886/2441 (mod 259269950887) = 223915085356
3259269950886/610429 (mod 259269950887) = 53534810325

U sa che 2, 3, 29 e 2441 sono primi, ma sospetta di 610429.

L'oracolo fornisce un certificato per 610429.
Fattorizzazione per 610429:
610429 = 22·3·7·13·43
e una base adatta: a = 2.

U verifica la fattorizzazione.
U calcola:
2610428 (mod 610429) = 1
2610428/2 (mod 610429) = 610428
2610428/3 (mod 610429) = 255876
2610428/7 (mod 610429) = 583168
2610428/13 (mod 610429) = 461598
2610428/43 (mod 610429) = 174519

U sa che 2, 3, 7, 13 e 43 sono primi. Pertanto è sicuro che anche 610429 è primo.

Non occorrono più certificati. 
Ora U è certo che N = 79925742525202824779 è primo!

L'algoritmo A riceve in input l'intero N.
A può fermarsi o non fermarsi.
Se A si ferma e risponde no, N è certamente composto.
Se A si ferma e risponde sì, N è certamente primo. Inoltre, in questo caso, A fornisce un certificato di primalità.

6. Co-problemi e NP-completezza

La Definizione 6 di classe NP, conduce immediatamente ad una definizione complementare:

Definizione 8

Diciamo che un problema decisionale Q appartiene alla classe co-NP
se ogni istanza no di Q può essere verificata in tempo polinomiale.

    Il grafo G è euleriano?

risponde anche, simultaneamente, alla domanda:

    E' vero che G non è euleriano?

Si ha quindi, banalmente, che la classe P è contenuta nella intersezione di NP e co-NP.

Ben diversa è la situazione per gli algoritmi non-deterministici.

Esempio di asimmetria tra istanze sì ed istanze no per gli algoritmo non-deterministici

Consideriamo il Problema del Grafo Hamiltoniano. Abbiamo già osservato che esso è in NP. Ogni istanza sì del problema può essere verificata in tempo polinomiale. Consideriamo ora una istanza no, un grafo G non-hamiltoniano, e supponiamo di non essere in grado di provarlo. Chiediamo all'oracolo:

E' vero che G non è hamiltoniano?

L'oracolo ci risponde sì. Noi non ci fidiamo, vogliamo un certificato. Ma quale? Siamo noi a doverlo dire. Quali dati ci possono essere forniti, che in tempo polinomiale ci conducano alla conclusione che non esiste nel grafo alcun circuito hamiltoniano? Nessuno sa rispondere a questa domanda.

Per esempio, abbiamo visto nel Teorema 4 che il Problema del Riconoscimento dei Numeri Composti è in NP. Segue subito che il suo co-problema, il Problema del Riconoscimento dei Numeri Primi, è in co-NP. Abbiamo visto nel paragrafo precedente quanto è stato difficile provare che il Problema del Riconoscimento dei Numeri Primi è in NP!

Dopo il 2002, come conseguenza del teorema AKS, è noto che il Problema del Riconoscimento dei Numeri Primi è in P. Questo rende (ora) ovvio il fatto che esso sta sia in NP che in co-NP.

Si noti che non siamo attualmente in grado di rispondere ai problemi:

La classe NP coincide con la classe co-NP?

La intersezione della classe NP con la classe co-NP è esattamente P?

Esiste, nella classe NP, un problema che sia più difficile di tutti gli altri problemi in NP? In altri termini esiste un problema T in NP tale che

per ogni Q in NP si ha Q ® T?

Definizione 9

Un problema decisionale T si dice NP-completo se valgono:

1) T appartiene a NP
2) Se Q appartiene a NP allora Q ® T

Dall'anno del fondamentale lavoro di Cook, sono state trovate centinaia di problemi NP-completi. Questo insieme di vette della difficoltà computazionale comprende i più importanti e duri problemi che emergono sia dalla combinatorica, la teoria dei numeri e altre discipline della Matematica pura, che da settori concreti ed applicati come la programmazione industriale!

I problemi 4 - 11 del nostro elenco, sono tutti NP-completi.

Una caratteristica dei problemi NP-completi è che, sovente, rimangono tali anche se si diminuisce drasticamente la grandezza dello spazio di ricerca. Si pensi ai probemi del Grafo Hamiltoniano e alla sua restrizione: in un caso si deve considerare un grafo qualsiasi, nell'altro ci si può limitare a grafi planari con esattamente tre archi incidenti in ogni vertice!

Un altro caso sorprendente dello stesso fenomeno si ha per il Problema della Congruenza Quadratica Limitata. Esso rimane NP-completo anche se ci vengono dati gratis (cioé senza spesa di tempo di calcolo):
1) La fattorizzazione di B, diciamo B = p₁^e₁ p₂^e₂ ... p_k^e_k
2) Per ogni potenza p_i^e_i, le soluzioni di x² = A (mod p_i^e_i)

Le due classi sono uguali se una macchina deterministica è in grado di fare le stesse cose di una macchina non-deterministica.

Sono uguali se il dono della ubiquità non conta nulla, se l'illimitato parallelismo non fa differenza, se esplorare infinite distese di numeri è inessenziale, basta un po' di serendipity, se ciò che un onesto, concreto programma può realizzare coincide con le nostre fantasie, i nostri sogni più audaci.

Se, alla fin fine, dell'oracolo non sappiamo che farcene!

Q appartiene a NP

Q non appartiene a P

La prima consiste nel prendere un problema difficile in NP e dimostrare che non esistono algoritmi polinomiali che lo possano risolvere.

Questa strada appare del tutto impraticabile.

La seconda via cerca una soluzione polinomiale di un problema NP-completo. Se, per esempio, si trovasse un algoritmo che in tempo polinomiale risponde ad ogni istanza del Problema dello Zaino, si potrebbe, utilizzando le funzioni di riduzione, risolvere in tempo polinomiale qualsiasi problema in NP, con il formidabile risultato di aver così dimostrato che P è uguale a NP.

7. Giochi veramente difficili

Il primo gioco che prendiamo in considerazione è "Campo Minato" (Minesweeper), presente nella cartella Giochi di tutti i sistemi Windows. Ecco le istruzioni (copiate dalla Guida):

Per giocare una partita di Campo minato: inizio del gioco

1    Scegliere Nuova dal menu Partita.
2    Fare clic su una casella qualsiasi del campo di gioco per avviare il timer.

Note e suggerimenti

Lo scopo del gioco consiste nel riuscire a individuare tutte le mine sul campo di gioco, senza scoprirle, nel più breve tempo possibile.

L'area di gioco di Campo minato è costituita dal contatore di mine, dal timer e dal campo di gioco.
Per scoprire una casella, fare clic sulla casella con il pulsante sinistro del mouse. Se la casella contiene una mina, la partita sarà considerata persa.
Se la casella contiene un numero, questo indica il numero di mine situate nelle otto caselle circostanti.
Per contrassegnare una casella come mina, fare clic sulla casella con il pulsante destro del mouse.

Figura 9

Domanda: C'è una mina dove è posto il punto interrogativo?

Chiaramente, se mettiamo numeri tra 0 e 8 a caso in una griglia nxn, non sempre otterremo una configurazione valida, ovvero una configurazione che viene da una reale disposizione di mine.

Abbiamo allora un problema decisionale:

Problema del Campo Minato
Istanza generica:

• Dati: Una griglia nxn contenente in certe posizioni numeri (compresi tra 0 e 8) e bandiere (che indicano "casella libera")
• Domanda: La configurazione è valida?

Figura 10

In questo caso la risposta è no, la configurazione non è valida.

Il problema del Campo Minato sta ovviamente nella classe NP. L'oracolo ci può convincere di una istanza sì, semplicemente mostrandoci un campo minato compatibile con i dati della istanza.

E' stato dimostrato nel 2000, da Richard Kaye, che Il problema del Campo Minato è NP-completo!

Lo stesso vale per il ben noto gioco del Sudoku, che ormai è presente su quasi tutti i giornali e le riviste illustrate.

Un Sudoku è una griglia di 9x9 caselle in ognuna delle quali si dovrà scrivere un numero, da 1 a 9.
La griglia è a sua volta divisa in 9 quadratini di 3x3 caselle.
Il gioco consiste nel riempire la griglia in modo tale che alla fine in ogni colonna, in ogni riga e in ogni quadratino, ogni numero appaia una volta sola.

Problema del Sudoku
Istanza generica:

• Dati: Una griglia G n²x n² contenente n² quadratini nxn nei quali sono disposti alcuni interi compresi tra 1 ed n²
• Domanda: Si può completare G in modo tale che in ogni riga ed in ogni colonna di G gli interi tra 1 e n² appaiano una ed una sola volta, e siano al tempo stesso tutti presenti in ogni quadratino?