Inspiriert von der Frage, ob Factoring als P-hart bekannt ist , frage ich mich, wie der derzeitige ähnliche Wissensstand die Härte des Graph-Isomorphismus betrifft. Ich bin sicher, dass derzeit nicht bekannt ist, ob GI in P ist, aber:
Was ist die derzeit bekannteste größte Klasse, die GI schwerer ist als?
(es wurde bei einer ähnlich klingenden Frage nicht beantwortet )
Um auf einige der Kommentare einzugehen, möchte ich die derzeit bekannten maximalen Klassen kennen, für die das Problem vollständig ist. Bekannte Algorithmen für GI sind durch Superpolynomfunktionen begrenzt, und es ist ein Mitglied von NP. Es ist jedoch nicht bekannt, dass GI P-hart ist. Ich würde gerne die Klassen C kennen, für die es bekanntermaßen C-schwer und hoffentlich so umfassend wie möglich ist.
Antworten:
Dies scheint das bisher stärkste Härteergebnis zu sein.
quelle