En el documento "Un Compendio de problemas completos para P" de Greenlaw, Hoover y Ruzzo (PS) (PDF) , hay una lista de problemas en P que no se sabe que están en Carolina del Norte y que tampoco se sabe que están completos en P . (Esta lista incluye todos los problemas abiertos en la excelente encuesta realizada por Karp y Ramachandran ). La lista abierta de problemas comienza en la página 89.
¿Cuántos problemas de esta lista se han resuelto (es decir, se ha demostrado que están completos en P o en NC)? Supongo que no se han resuelto demasiados en los últimos 19 años, por lo que (con suerte) no debería convertirse en una gran lista.
Esa es la lista más reciente que pude encontrar. ¡También se agradecerían los indicadores a una lista más actualizada!
EDITAR: András Salamon señala que hay un libro de texto de los mismos autores que tiene una lista un poco más larga. Este es un PDF del libro. Los problemas abiertos comienzan en la página 237.
fuente
Respuestas:
Por cierto: la lista de problemas conocidos de CC-complete ha crecido desde ambas versiones del libro. Ver este artículo de Greenlaw y Kanlabutra.
fuente
Angelo Monti, Sobre la complejidad computacional de los cierres de gráficos Cartas de procesamiento de información, Volumen 57, Número 6, 25 de marzo de 1996, páginas 291–295.
fuente