Dr PyvivMar 21
@tanavit en fait, les problèmes sont démontrés comme étant équivalent : on peut utiliser la solution de l'un pour en résoudre un autre. En gros, on peut coder la division des grands nombres avec des flips de triangulations
Show threadPffff...Mar 21
@pyviv @tanavit Mais il me semble qu'on n'a pas prouvé que NP dur est inclus dans NP complet, ce qui laisse la place à des problèmes plus difficiles. (Je dis peut être une bêtise, c'est pas mon domaine.)
Show threadFrédéric Grosshans

@1HommeAzerty @pyviv @tanavit On sait que NP-dur n'est pas inclus dans NP-complet, car il y a des problèmes strictement plus difficiles que NP.

Par définition NP-dur signifie «au moins aussi compliqué que NP», donc ça inclut les problèmes EXPSPACE (qui peuvent être résolus avec une taille mémoire exponentielle) une classe strictement plus grande que PSPACE (ceux qui peuvent être résolus avec une mémoire polynomiale), or tout problème NP peut être résolu avec une mémoire polynomiale (NP est dans PSPACE). N'étant pas théoricien de la complexité moi même, je ne sais pas comment démontrer que PSPACE ≠ EXPSPACE, je sais juste que ça s'appelle le «theorème de la hiérarchie polynomiale»

Mar 21 at 8:36amWeb