
Neues Resultat: Graphenisomorphie-Problem quasipolynomiell lösbar?
Die Frage, wie man wie schnell überprüfen kann, ob zwei Graphen eigentlich gleich sind, ist eine höchst knifflige. In Mathematik und Informatik wird das Problem des Graphenvergleichens als das "Graphen-Isomorphie-Problem" gehandelt - und ist dort ziemlich hoch angesiedelt.
Zweimal derselbe Graph? Oder doch zwei…