Si l'isomorphisme graphique est dans P, est alors p = np?
-
05-11-2019 - |
Question
Je pense que, puisque l'isomorphisme graphique n'est pas connu pour être $ textbf {np} $-Callete, nous ne pouvons pas réduire tous les problèmes $ textbf {np} $ à lui, et donc l'implication ne tient pas.
En outre, dans la réponse acceptée à cette question il est indiqué qu'une preuve que l'isomorphisme graphique n'est pas $ textbf {np} $-Ccomplete prouverait $ textbf {p} neq textbf {np} $. Pourquoi?
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange