Pagina Radice del Progetto: Graph Isomorphism

Fatti da conoscere:

concetti di isomorfismo ed automorfismo;
conoscenza elementare di teoria dei gruppi (basta poco);
la gerarchia polinomiale;

Approfondire entrambi i seguenti due argomenti:

se Graph Isomorphism è NP-completo allora la gerarchia polinomiale collassa al secondo livello;
giochi di Mago Merlino e Re Artù. Esempi di tali protocolli nel caso di alcuni problemi di isomorfismo.

Volendo poi eventualmente spingersi oltre, sarebbe interessante poi derivare da alcuni specifici protocolli Merlino-Artù per problemi di isomorfismo, interessanti conseguenze quali ad esempio il fatto che Graph Isomorphism è in co-NP(SPARSE). (Ossia è possibile certificare una risposta negativa al cospetto di una famiglia polinomiale di circuiti).

Come riferimento, per la gerarchia polinomiale resta sempre una buona idea partire dal libro:

Christos H. Papadimitriou,
Computational Complexity,
Addison-Wesley Publishing Company, Reading, MA, (1994).
ISBN: 0-201-53082-1

Più precisamente:

il Capitolo 17 The polynomial hiearchy.

Tuttavia sarà poi indispensabile muoversi al seguente testo (che però è più leggero ed anche contiene una sua introduzione alla gerarchia polinomiale).

Johannes Koebler, Uwe Schoening, Jacobo Toran,
The Graph Isomorphism Problem: Its Structural Complexity,
Birkhauser Boston, (1993).
ISBN: 0-8176-3680-3
ISBN: 3-7643-3680-3

In entrambi i casi, le matrici di quanto serve sono disponibili all'ufficio fotocopie.

created: 7 aprile 2003
updated: 7 aprile 2003