Redundancja i struktura problemów obliczeniowych

Powszechnie uważa się, że niektóre problemy obliczeniowe, takie jak izomorfizm grafów, nie mogą być NP-kompletne, ponieważ nie mają wystarczającej struktury lub redundancji, aby były trudne obliczeniowo (NP-twarde). Interesują mnie różne pojęcia formalne dotyczące struktury problemów obliczeniowych i miar redundancji.

Jakie są główne znane wyniki takich formalnych pojęć dotyczących problemów obliczeniowych? Ostatnia ankieta dotycząca takich pojęć byłaby bardzo miła.

EDYCJA: Wysłany na MathOverflow

cc.complexity-theory graph-isomorphism

— Mohammad Al-Turkistany
źródło

$\mathsf{coAM}$ $\mathsf{NP}$ $\mathsf{NP}$

$\mathsf{NP}$

(Z drugiej strony, izomorfizm grupy wydaje się nawet bardziej ustrukturyzowany niż GI, ale nie jest znane zmniejszenie liczenia do decyzji dla grupy iso. Być może to mówi, że GI jest w pewnym sensie „odpowiedniej strukturze” - zbyt struktury, aby być kompletne NP, ale wystarczająco nieuporządkowane, aby umożliwić zmniejszenie liczby decyzji do decyzji).

— Joshua Grochow
źródło

Zatem GI w pewnym sensie nie jest wystarczająco „losowy”, aby uchwycić kompletność NP. Czy istnieje jakieś pojęcie formalne, które wychwytuje taki brak losowości problemu z OG?

— Mohammad Al-Turkistany

Tak, jednym z takich założeń jest to, że OG nie jest kompletny NP! :-) (Chyba że załamie się hierarchia wielomianowa.)

— Scott Aaronson

Jacobo Toran stwierdza: „Istnieje powszechne przekonanie, że GI nie zawiera wystarczającej struktury lub nadmiarowości, aby było trudne dla NP”, NA TWARDOŚCI ISOMORFIZMU GRAF, SIAM Journal on Computing, 33 (5), 1093–1108. Problem polega na tym, że nie wiemy, jak udowodnić brak twardości NP naturalnych problemów NP.

— Mohammad Al-Turkistany

Myślę, że być może stwierdzenie Torana i moje to dwie strony tego samego medalu: moje mówi, że poszczególne przypadki problemów są zbyt ustrukturyzowane, a jednym z nich jest to, że ogólny język GI nie jest wystarczająco zbędny (oświadczenie Torana). Myślę. Trudno powiedzieć bez pytania Jacobo.

— Joshua Grochow