Pspace=exptime ?

Bound

Bonjour à tous.

Il s'avère que le problème des dames généralisées est à la fois EXPTIME-Complet (voir la preuve : https://www.semanticscholar.org/paper/N-by-N-Checkers-is-Exptime-Complete-Robson/d715b140e4787a88423437d62ed632b53b26907d ) et PSPACE-Complet (voir la preuve : https://ieeexplore.ieee.org/document/4567962 ) Vu que le problème est à la fois EXPTIME-Complet et PSPACE-Complet, EXPTIME=PSPACE.

Merci de dire ce que vous en pensez.

Math Coss

Du mal mais pour des mauvaises raisons... Les références que tu présentes ont plus de trente ans. Or il y a huit ans, le problème était apparemment encore considéré comme ouvert – avec une réponse plutôt opposée, à savoir EXPTIME ≠ PSPACE. J'ai du mal à penser qu'une inférence si simple soit légitime dans ces conditions.