Problemas entre NC y P: ¿Cuántos se han resuelto de esta lista?

20

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.

Robin Kothari
fuente
@ Robin, por favor CW.
Mohammad Al-Turkistany
55
@turkistany: Dado que esta pregunta muy similar ( cstheory.stackexchange.com/q/1265/206 ) se consideró no necesariamente CW, no estoy seguro de si esto debería ser CWed. Seguiré la política de preguntas frecuentes "En caso de duda, no marque una pregunta CW" y esperaré más opiniones.
Robin Kothari
@ András: Gracias. Lo agregaré a mi publicación. Parece una lista un poco más larga de los mismos autores.
Robin Kothari

Respuestas:

12

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.

Paul Beame
fuente