Leí acerca de NPC y su relación con PSPACE y deseo saber si los problemas de NPC se pueden resolver de manera determinista utilizando un algoritmo con el requisito de espacio polinomial en el peor de los casos, pero potencialmente tomando tiempo exponencial (2 ^ P (n) donde P es polinomial).
Además, ¿se puede generalizar a EXPTIME en general?
La razón por la que pregunto esto es que escribí algunos programas para resolver casos degenerados de un problema de NPC, y pueden consumir cantidades muy grandes de RAM para instancias difíciles, y me pregunto si hay una mejor manera. Para referencia, consulte https://fc-solve.shlomifish.org/faq.html .
fuente
Si. Aquí hay un boceto de una prueba directa.
fuente