Non sempre un'equazione a coefficienti interi ha soluzioni intere. Abbiamo avuto già modo di discuterne parlando del Decimo Problema di Hilbert, nel corso della prima parte. Anche se ci restringiamo a equazioni lineari (cioè di primo grado) in 2 incognite
x, y
troviamo situazioni disparate. Per esempio2x + 4y 1
non ha soluzioni intere perché I è dispari e, per ogni scelta di
X, Y
interi, 2X + 4Y è pari. Invece2x + 3y = 1
ha la soluzione intera
X =
—1, Y = 1. Il problema che ci interessa (quello delle equazioni lineari a coefficienti interi) ammette appunto• INPUT: un'equazione
ax by = e
con a,b, c
E Z, a,b
non entrambi nulli e richiede• OUTPUT: SÌ/NO a seconda che ci siano o no interi
X, Y
che la soddisfano(aX bY = c).
Un minimo di dimestichezza con l'algebra ci mostra che ax + by = c ha soluzioni intere se e solo se il massimo comun divisore (a, b) di a, b divide
c.
Infatti, se ci sono X, Y E Z per cui aX + bY = c, (a, b), che è divisore di a e b, tramite X, Y divide anche aX + bY, cioè c.
Viceversa, l'identità di Bézout assicura che ci sono due interi X, Y per cui aX + bY = (a, b)
e la proprietà si trasmette ovviamente ad ogni multiplo c di (a, b). Anche in vista di successive applicazioni nei prossimi paragrafi, ricordiamo in maggior dettaglio la prova dell'identità di Bézout. Tutto nuovamente si basa sull'al-goritmo euclideo delle divisioni successive per la ricerca del massimo comun divisore (a, b) di a, b: per a > b > O, si divide a per b, b per l'eventuale resto non nullo ro , e così via finché non si trova un resto nullo r s ; l'ultimo resto non nullo rs _ i è (a, b).
Se la procedura si ferma subito, cioè (a, b) = b, b si scrive a • O b • 1, dunque si pone X = O, Y = 1. Altrimenti, si procede per induzione sul numero s dei passi necessari per determinare (a, b). Ammettiamo così di aver ottenuto la decomposizione di (b, ro ) (il cui calcolo richiede un passo in meno rispetto ad (a, b)) e di aver provato (b, ro ) = bX' + ro Y' per X' ,Y' interi opportuni;
ricordiamo a — bqo = ro per qualche qo e deduciamo
(a, b) = (b, ro ) = bX' + roY' = + (a —
bq0 )Y 1
=aY'
b(X' — q o Y'), così X = Y' e Y =X'
— qor soddisfano quanto l'identità di Bézout richie-de. Anzi si noti che X, Y così determinati hanno lunghezza polinomialmente limitata da quella dei coefficienti a, b, c. Infatti, la proprietà è ovvia quando X = O, Y = 1, e si preserva ad ogni passo induttivo; così ci basta ricordare che X ,Y sono calcolati entro S passi dove S < log2 N.Torniamo adesso al nostro problema di esistenza di soluzioni intere per ax + by = c. È facile tracciare un programma che lo risolve: dati a, b, c,
• calcoliamo (a, b) (per esempio tramite l'algoritmo euclideo delle divisioni successive),
• controlliamo poi se (a, b) divide o no c.
L'esistenza di soluzioni intere corrisponde infatti ad una risposta positiva al-l'ultima verifica.
Questa procedura pone il problema in P. Infatti i tempi di lavoro sono più o meno quelli dell'algoritmo di Euclide, visto che la divisione finale di c per
(a, b) e il calcolo del relativo resto non incidono significativamente, e sap-piamo dal Capitolo 7 che il procedimento di Euclide impiega tempo al più polinomiale, anzi quadratico, rispetto alla lunghezza degli input a, b.
4. PRIMI
L'ultimo esempio che vogliamo citare riguarda un problema famoso e datato, che risale ai tempi di Euclide, e dunque a 2 millenni or sono, e anche più.
È dato:
• INPUT: un intero N > 1; ogni intero maggiore di 1 si decompone in modo unico nel prodotto di fattori primi. Come si vede, la questione è duplice. Infatti, per N composto, a) si ac-contenta di saperlo, b) pretende invece di conoscere i divisori non banali di N.
a) è poi un problema di decisione, b), invece, un problema di computazione.
Come detto, la questione è classica, eppure ancora attuale, visto che molti protocolli crittografici (usati per esempio per garantire transazioni sicure in rete), si basano sulle attuali conoscenze e ignoranze su algoritmi di primalità e fattorizzazione. Pur tuttavia, metodi molto semplici riescono a soddisfare l'una e l'altra questione. Vediamone uno.
Dato N, si divide N per ogni numero q tale che 1 < q < N. Se la divisione non è mai precisa (cioè non dà mai resto 0), si può dedurre che N è primo;
altrimenti, se N = q • q' per qualche q con 1 < q < N e per un opportuno corrispondente q', ancora soddisfacente 1 < < N, allora si può dichiarare N composto e si hanno informazioni sulla sua decomposizione (anche se, per ottenere tutti i fattori primi di N, bisognerà applicare la procedura a q, j e poi ulteriormente, finché necessario).
Tutto questo era noto già ai tempi di Euclide e degli antichi greci. Perché dun-que l' algoritmo non ci basta? La risposta è che esso richiede N — 2 divisioni, quindi un numero di passi almeno esponenziale rispetto al logaritmo di N e quindi, in definitiva, rispetto alla lunghezza di N.
È vero che la procedura si può accelerare; per esempio è sufficiente appli-carla ai valori q con 2 < q < N/Kr (Esercizio. Perché?). Tuttavia que-ste semplificazioni non bastano ad evitare il carattere esponenziale: infatti
L__ N = 2
1°Y2 ',
è ancora esponenziale rispetto a log2 N.
In effetti, solo nell'agosto del 2002 tre informatici indiani (Agrawal, Kayal, Saxena [2], [3]) hanno determinato un algoritmo che risolve il problema di primalità lavorando in tempo al più polinomiale nella lunghezza di N (circa 0(log2 1 N), a meno di fattori di minor significato). La procedura di Agrawal, Kayal, Saxena, già denotata AKS dalle iniziali dei suoi autori, è relativamente complicata, richiede conoscenze di algebra astratta e di combinatorica e tra-scende certamente gli obiettivi di queste note. Comunque colloca finalmente il problema della primalità in P (concludendo in questo modo un itinerario di ricerca durato oltre 2 millenni).
Terminiamo l'esempio con due commenti:
• AKS, pur ottimo in teoria, non è ancora gran che utilizzato nella pratica.
Computazioni di grado 11 nella lunghezza dell'input risultano proibitive
nelle applicazioni. Si continuano a preferire, per la primalità, procedure di carattere probabilistico, passibili di errori nelle loro risposte "N primo" o
"N composto", pur tuttavia rapide nella pratica e abbastanza affidabili (ca-paci cioè di minimizzare l'eventualità di sbaglio). Ne parleremo tra poco.
L'osservazione comunque mostra quanto la teoria e la pratica possono essere distanti anche per P.
• AKS, pur risolvendo egregiamente in teoria il problema della primalità, non dà sviluppi significativi per l'altra questione, quella della decomposizione in fattori primi. In quest'ultimo ambito, procedure al più polinomiali so-no ancora scoso-nosciute (a meso-no che certi sviluppi della fisica quantistica non permettano di rivedere in modo sostanziale i concetti di calcolatore e computazione: ne accenneremo alla fine di questo libro).
In riferimento all'ultimo esempio (quello dei primi e dei composti) possiamo an-che fare la seguente banale osservazione. Per come abbiamo impostato il proble-ma, ci aspettiamo la risposta
• SÌ, se il dato input N è primo,
• NO, se N è composto.
L'accento positivo è sulla primalità. Ammettiamo adesso di invertire la domanda, e chiedere "N è composto o no?". La risposta adesso sarà
• SÌ, se N è composto,
• NO, se N è primo.
Non c'è da immaginare, però, che il cambio della domanda possa mutare i tempi di lavoro, rallentarli, o accelerarli. Infatti, i procedimenti per la primalità funzio-nano ancora, si tratta solo di invertire la conclusione: se si è risposto ,tN0 alla domanda se "N è primo", si dice NO/SÌ se la domanda diventa "N è composto".
Tutto questo è assolutamente ovvio. Così, in generale, possiamo anche porre, se vogliamo, la seguente definizione.
Definizione. coP è la classe dei problemi S su alfabeti A tali che A* — S (il complemento di S) è in P.
D'altra parte, per w E A*, w E A* — S se e solo se w S. Così A* — S ha risposta SÌ/NO esattamente quando S ha risposta NO/SÌ. Dunque, banalmente, coP = P.
Nel seguito, per S C A*, denoteremo spesso Sc il complementare A* — S di S.
Esercizio. Si provi che, se S è un insieme finito di parole su un alfabeto A, allora S E P.
8.2 La classe NP
Ritorniamo all'esempio 2 del precedente paragrafo, quello relativo a 2SAT. Ac- cettiamo adesso come input insiemi finiti di clausole di lunghezza superiore a 2,
e
come
{POP1P2P3P4, POP1P2P3P4 P2P4P5P6 },
per valutarne la soddisfacibilità. Il relativo problema si indica con la sigla SAT, (dall'inglese satisfiable, soddisfacibile) e generalizza 2SAT. Ma l'algoritmo per 2SAT e il relativo effetto domino adesso non valgono più perché sono ovviamen-te legati alla lunghezza 2 delle parole coinvolovviamen-te; anzi, riesce difficile elaborare procedure alternative di soddisfacente velocità.
In effetti, quel che cerchiamo è una valutazione v di tutte le lettere coinvolte nelle parole in input, che assegna il valore 1 ad una lettera (maiuscola o minuscola) in ogni clausola (equivalentemente una parola che intersechi ogni clausola in almeno una lettera). Ora, se n sono le lettere coinvolte nelle nostre clausole,
• 290,731, le relative versioni minuscole,
• Po, P1, , Pn i le corrispondenti maiuscole,
le valutazioni v da indagare sono T: ogni v può infatti assegnare, per ogni i < n, a pi valore O oppure 1, e conseguentemente 1 o O ad
R.
Notiamo che l'indice n è parametro significativo della lunghezza dell'insieme finito di clausole che fa da input. Cosi una indagine su tutte le possibili v è da ritenersi almeno esponenziale nella lunghezza dell'input, e quindi è chiamata ad esaminare "troppi" casi.Ammettiamo però di conoscere una valutazione v giusta (seppur esiste). Control-lare che v funziona, rilevare cioè che ogni clausola dell'input ha una lettera cui v associa 1, non è significativamente più lungo che leggere l'input stesso. Così la re-lativa verifica, conoscendo v, è rapida rispetto alla lunghezza dell' input. Ricordia-mo poi che le informazioni essenziali su v, cioè i suoi valori su m, pi, ,
possono sintetizzarsi in un'unica parola di lunghezza < n, come abbiamo visto nel precedente paragrafo. Per esempio popiP2 può rappresentare la valutazione v per cui v (130) = v (pi) = 1, v (p2) = O. Si noti che pope P2 interseca le tre clausole dell'insieme proposto poche righe fa, gP1p2 P3 P4 in po, PopiP2p3 P4 in
pi e P2P4P5P€ in P2.
La classe NP è quella che include i problemi che hanno questa stessa caratteri-stica di SAT, nel senso della seguente definizione (1(w) denota qui e in seguito la lunghezza di un input w).
Definizione. NP è la classe dei problemi di decisione S su alfabeti finiti A per i quali esistono
• S' C A*, S' E P
• un polinomio ps a coefficienti interi (e a valori positivi)
tali che, per ogni w E A*, w E S se e solo se esiste y E A* per cui (w, y) E 8' e 1(y) < ps (1(w)).
Esempi.
1. Come già detto, SAT, o anche nSAT (la sua variante ristretta ad input co-stituiti da insiemi finiti di clausole di n lettere) per n > 3, sono in NP. Altri esempi li accompagnano.
2. Consideriamo infatti 3COL (il problema della 3-colorabilità di grafi finiti).
Formalmente, 3COL può intendersi come l'insieme dei grafi finiti (V, E) per cui esiste una 3-colorazione e : V ---> {1, 2, 3} tale che, per v, w E Ve
(v, w) E E, c(v) c(w) . Così 3COL è la variante del problema 2COL (già considerato e collocato in P) quando i colori ammessi sono 3.
Non è evidente che 3COL stia ancora in P, l'algoritmo polinomiale di 2COL è troppo legato all'ipotesi dei 2 colori. Del resto le possibili colorazioni c sono, per IV! = n, 3n, tante quante le funzioni dagli n vertici di V ai 3 colori { 1, 2, 3}; esplorarle una ad una è procedura esponenziale in n. Si può obiettare che, se una colorazione c funziona, tutte le colorazioni d che si ottengono da c componendola con una permutazione dei colori 1, 2, 3, funzionano ancora. In altre parole, per concludere che (V, E) E 3COL, non è tanto importante come si colora un dato vertice, se di 1, o di 2, o di 3, ma che i vertici adiacenti in E abbiano colori diversi. Così se c soddisfa
c(v) c(v') per ogni scelta di v, vi E V con (v, v') E E, e a permuta 1, 2, 3, allora anche o-c mantiene la proprietà
ac(v) ac(v') per ogni scelta di v, vi come sopra .
Quindi potremmo limitare la nostra analisi trascurando le possibili o- c al varia-re di a, quando c è già stata controllata. Purtroppo le permutazioni su 3 oggetti sono 3! = 6, e dunque l'osservazione riduce il numero dei casi da esplorare da 3n a `11 , mantenendolo comunque al livello esponenziale.
D'altra parte, una singola colorazione c è individuata dai colori associati agli n vertici di V e cioè da una n-upla ordinata in {1, 2, 3} (e dunque ha lunghezza direttamente collegata ad n). Se poi c funziona, verificarlo, cioè controllare che vertici distinti assumono colori distinti in e, è impegno che si limita ad una
"lettura" (ad una osservazione complessiva) del grafo (V, E), e quindi non ne eccede in modo significativo la lunghezza.
Ne deriva che 3COL E NP. Lo stesso vale per mCOL (grafi coloratili a m colori) per ogni m > 3 come il lettore può formalizzare in dettaglio, se vuole.
3. Consideriamo ora equazioni in 2 incognite a coefficienti interi, come nell'e-sempio 3 del precedente paragrafo. Ammettiamo tuttavia grado 2, e comunque esaminiamo
• INPUT: un'equazione aw 2 by = c con a, b, c interi, a O, e nuovamente cerchiamo
• OUTPUT: SÌ/NO secondo che l'equazione abbia o no soluzioni intere.
Così
x2 =
3 (cioè a = 1, b = O, e = 3) ha risposta negativa perché 3 non è quadrato di nessun intero;x2 +
4y = 4 (cioè a = 1, b = 4, c = 4) ha risposta positiva (perché risolta da (+2, 0), o da (0, 1), e così via).Il procedimento usato per le equazioni lineari (cioè sostanzialmente, 1' algo- ritmo euclideo delle divisioni successive) è intrinsecamente legato al grado
1, e non può estendersi alla nuova situazione: varrebbe infatti a determinare l'esistenza di possibili soluzioni intere X', Y' per l'equazione lineare
aX' + bY' = c,
ma non a garantire che X' =
x2
si esprima come quadrato di un intero. Sem-mai possiamo ricordare quanto osservato nell'esempio 3 del paragrafo 8.1 e cioè che la lunghezza delle possibili soluzioni X t , Y' è polinomialmente li-mitata rispetto a quella dei parametri a, b, c; tramite quindi, risulta po-linomialmente limitata anche la lunghezza di un eventuale intero x per cui X' = x2 .Ritorniamo allora alla nostra equazione di secondo grado ax2 by = c. Dalle precedenti considerazioni deduciamo che le soluzioni intere, se esistono, han-no lunghezza limitata da quella dei coefficienti. Allora calcoliamo quanti sohan-no gli interi X o Y di una data lunghezza l > 1 in base 2. Il loro numero è 2 -1 perché essi si compongono di l cifre, ciascuna delle quali può assumere i va-lori 0, 1, salvo la prima che è ovviamente 1. Per esempio, i numeri di 4 cifre in base 2
1000
, 1001, . .
. 4111
sono 23 = 8.
Possiamo cercare le possibili soluzioni intere della nostra equazione prima fis-sandone la lunghezza (limitata!) e poi procedendo per tentativi, coinvolgendo cioè ogni possibile coppia (X, Y) di lunghezza lecita l; ma si tratta di un mec-canismo esponenzialmente lungo essendo 22-1 i casi da esaminare per X o per Y, fissata l. Pur tuttavia, se la soluzione (X, Y) è nota, verificarla, controllare cioè aX 2 bY = c, è compito che si può svolgere con rapidità.
In conclusione, ax2 by = c ha radici intere se e solo se esistono X, Y di lunghezza polinomialmente limitata da quella di a, b, e per cui aX2 bY = c.
Il problema è quindi in NP.
In previsione di sviluppi futuri, allunghiamo ancora la nostra lista di esempi in NP.
4. Consideriamo adesso grafi finiti G = (V, E). Introduciamo le seguenti defini-zioni: un sottoinsieme V0 di V si dice
• indipendente se, per ogni scelta di v, E V0, (v, v') E;
• un ricoprimento di vertici se, per ogni scelta di v, li E V con (v, v') E E, v E Vo o vi E Vo;
• una cricca (in inglese, clique) se, per ogni scelta di v, if E Vo con v v', (v, v i ) E E.
Ricordiamo che la nostra definizione di grafo esclude (v, v) E E per v E V.
Ci interessano i seguenti tre problemi.
a) I S = problema dell'insieme indipendente.
• INPUT: (V, E) grafo finito, k intero positivo minore o uguale della cardi-nalità [VI di V: