grafi isomorfi

[illy]

qualcuno ha idea se esiste un algortitmo efficiente in c o c++ che restituisca, dati 2 grafi, se questi (rinominado eventualmente i vari nodi) sono isomorfi?

[Ziosilvio]

Algoritmi come quello che chiedi non sono noti.

Curiosamente, il problema dell'isomorfismo di grafi non è noto essere NP-completo; anzi, si congettura che sia uno di quei problemi NP che non sono né in P né NP-completi, di cui la congettura "P è diverso da NP", se vera, assicura l'esistenza.

Ancora più curiosamente, il problema dell'isomorfismo di sottografi è NP-completo: maggiori informazioni QUI.

[illy]

ooooops....
non ho capito niente....

[fuocofatuo]

Posso accennarti una spiegazione, anche se una fornita da Ziosilvio sarebbe sicuramente più completa.

Avrai già sentito parlare di complessità computazionale, intesa come lo sforzo impiegato da un certo algoritmo per ottenere un risultato, dato un input di una certa dimensione (taglia). Avrai così sentito parlare di algoritmi quadratici, lineari e via dicendo.
É però possibile studiare anche la complessità dei problemi, invece che dei singoli algoritmi: così facendo, ad esempio, possiamo stabilire che ogni soluzione algoritmica per un dato problema non può essere più efficente di una certa soglia.

Da questo tipo di studio, si sono dedotte diverse classi di complessità: si parla di P, NP, NP-completi, NP-difficili ecc ecc.
In particolare, la classe P è la classe dei problemi per cui esiste un algoritmo polinomiale che li risolva, ovvero un algoritmo O(n^k), con k costante. Questa è la sola classe che raccoglie problemi con algoritmi reputati efficienti.
Per i problemi NP, non conosciamo nessun algoritmo polinomiale, ma solo algoritmi (ad esempio) esponenziali; nulla vieta che, in futuro, qualcuno di questi problemi finisca col passare in P, scoprendo un algoritmo polinomiale che lo risolva (è successo, ad esempio, qualche tempo fa con il simplesso: prima di questo algoritmo, si pensava che la programmazione matematica lineare fosse "difficile", mentre ora si sa che non lo è).

Qual'è allora il problema: il problema è che non siamo perfettamente certi che P e NP siano insiemi diversi... Potrebbe darsi che, in realtà, tutti i problemi di NP siano risolvibili in tempo polinomiale, solo che noi non conosciamo tutti gli algoritmi...
In effetti non è stato ancora dimostrato che questo non è possibile, anzi, dimostrarlo sarebbe molto conveniente anche in termini economici: guarda qui ...

Si è molto convinti, comunque, che P sia diverso da NP: questo perchè esiste una classe di problemi, la classe degli NP-completi, che raccoglie i maggiori candidati a non essere in P. In particolare si ha che, trovando un algoritmo polinomiale per uno solo di questi, si otterrebbe automaticamente un algorimto polinomiale per ogni altro problema in NP, dimostrando P=NP.
Tuttavia, la classe degli NP-completi contiene centinaia di problemi noti, anche piuttosto comuni; si crede perciò che P e NP siano disgiunti, anche solo per il fatto che, per decenni, i problemi NP-C sono stati studiati dai più grandi matematici senza successo.

In particolare, quanto detto da Ziosilvio è perciò questo: essendo il problema da te proposto in NP, ma non in P o in NP-C, è nella posizione più ambigua possibile. I problemi di questo tipo possono finire, quasi in maniera capricciosa, tanto in P o quanto in NP-C; avrà allora il suo algorimto polinomiale se si dimostra che P=NP, così come se si dimostra che è P, chiaramente. Il problema dell'isomorfismo di sottografi, che non si doscosta molto dal tuo, è invece in NP-C: in tal caso, l'unica possibilità che questo abbia una soluzione efficiente è che P=NP, cosa ritenuta estremamente improbabile.

In altre parole, non è per niente facile che la determinazione dell'isomorfismo di due grafi sai risolubile in maniera efficiente, e men che meno è facile che lo sia l'isomorfismo di sottografi... Se proprio vuoi cercare un algortimo efficiente, però, cercalo per quest'ultimo: se mai lo dovessi trovare (e se mai dovesse esistere), entreresti negli annuali dei più grandi matematici e ti porteresti a casa un milione di dollari...

[illy]

magari....

grazie mille sei stato molto esauriente

[Ziosilvio]

Originariamente inviato da fuocofatuo

...
CUT
...
Se proprio vuoi cercare un algortimo efficiente, però, cercalo per quest'ultimo: se mai lo dovessi trovare (e se mai dovesse esistere), entreresti negli annuali dei più grandi matematici e ti porteresti a casa un milione di dollari...

Bellissima spiegazione, molto esauriente ed esatta tranne nel punto che ho quotato.
Purtroppo, i premi Clay sono assegnati a chi dimostra una delle sette congetture elencate sul sito della fondazione, ma non a chi le refuta: e dato che la congettura è "P è diverso da NP", chi dimostra che P=NP non prende neanche un centesimo.
Triste, ma sono le regole del gioco.

[fuocofatuo]

Mannaggia... e io che ci speravo!!!