Redondance et structure des problèmes de calcul

11

Il est largement admis que certains problèmes de calcul tels que l'isomorphisme des graphes ne peuvent pas être NP-complet car il ne possède pas suffisamment de structure ou de redondance pour être difficile à calculer (NP-hard). Je m'intéresse aux différentes notions formelles de structure des problèmes de calcul et des mesures de redondance.

Quels sont les principaux résultats connus sur ces notions formelles de problèmes de calcul? Une étude récente de ces notions serait très agréable.

EDIT: Publié sur MathOverflow

cc.complexity-theory graph-isomorphism Mohammad Al-Turkistany
la source

Réponses:

4

coAMNPNP

NP

(D'un autre côté, l'isomorphisme de groupe semble encore plus structuré que l'IG, mais aucune réduction du décompte à la décision n'est connue pour l'iso de groupe. Peut-être que cela dit que l'IG est en quelque sorte un niveau de structure "juste à droite" - trop structuré pour être NP-complet, mais suffisamment non structuré pour permettre une réduction du décompte à la décision.)

Joshua Grochow
la source
Ainsi, l'IG dans un certain sens n'est pas assez "aléatoire" pour capturer l'exhaustivité de NP. Existe-t-il une notion formelle qui capture un tel manque de caractère aléatoire du problème gastro-intestinal?
Mohammad Al-Turkistany
1
Oui, une de ces notions est que l'IG n'est pas NP-complète! :-) (À moins que la hiérarchie polynomiale ne s'effondre.)
Scott Aaronson
Jacobo Toran déclare "Il y a une croyance commune que l'IG ne contient pas assez de structure ou de redondance pour être difficile pour NP", SUR LA DURETÉ DE L'ISOMORPHISME GRAPHIQUE, SIAM Journal on Computing, 33 (5), 1093-1108. Le problème est que nous ne savons pas prouver la non-dureté NP des problèmes naturels de NP.
Mohammad Al-Turkistany, le
Je pense que la déclaration de Toran et la mienne sont peut-être les deux faces d'une même médaille: la mienne dit que les instances de problèmes individuels sont trop structurées, et un résultat de cela est que le langage global GI n'est pas suffisamment redondant (déclaration de Toran). Je pense. Sans vraiment demander à Jacobo, c'est difficile à dire.
Joshua Grochow