Shevek
@juanbellas Los problemas P son aquellos que se pueden comprobar en tiempo polinomial y, además, se pueden resolver en tiempo polinomial (por ejemplo, la división de dos números cuyo tiempo depende del número de cifras de forma suave y se comprueba con la multiplicación que es más sencilla).
Los problemas NP se pueden comprobar en tiempo polinomial pero no se ha encontrado un algoritmo de resolución polinomial (por ejemplo, la factorización de números).
El problema de las damas parece NP.
Shevek
@juanbellas Vale, lo encontré. Juzga tú mismo:
https://medium.com/@EthanZ/mastodon-is-big-in-japan-the-reason-why-is-uncomfortable-684c036498e5
Jonkman Microblog is a social network, courtesy of SOBAC Microcomputer Services. It runs on GNU social, version 1.2.0-beta5, available under the GNU Affero General Public License.
All Jonkman Microblog content and data are available under the Creative Commons Attribution 3.0 license.