Problèmes entre NC et P: combien ont été résolus à partir de cette liste?

20

Dans le document "A Compendium of Problems Complete for P" de Greenlaw, Hoover et Ruzzo (PS) (PDF) , il y a une liste de problèmes dans P qui ne sont pas connus pour être en NC et pas connus pour être P-complete non plus. . (Cette liste résume tous les problèmes ouverts dans l'excellente enquête de Karp et Ramachandran .) La liste des problèmes ouverts commence à la page 89.

Combien de problèmes de cette liste ont été résolus (c.-à-d. Montrés comme P-complets ou en NC)? Je suppose que pas trop de problèmes ont été résolus au cours des 19 dernières années, donc cela (espérons-le) ne devrait pas devenir une grande liste.

C'est la liste la plus récente que j'ai pu trouver. Des pointeurs vers une liste plus à jour seraient également appréciés!

EDIT: András Salamon souligne qu'il existe un manuel des mêmes auteurs qui a une liste légèrement plus longue. Ceci est un PDF du livre. Les problèmes ouverts commencent à la page 237.

cc.complexity-theory open-problem circuit-complexity Robin Kothari
la source
@Robin, Please CW.
Mohammad Al-Turkistany
5
@turkistany: Étant donné que cette question très similaire ( cstheory.stackexchange.com/q/1265/206 ) n'a pas été jugée nécessairement CW, je ne sais pas si cela devrait être CW. Je vais suivre la politique de la FAQ "En cas de doute, ne pas marquer une question CW" et attendre plus d'opinions.
Robin Kothari
@ András: Merci. Je vais l'ajouter à mon message. Il ressemble à une liste légèrement plus longue des mêmes auteurs.
Robin Kothari

Réponses:

12

BTW: La liste des problèmes connus de CC-complete s'est allongée depuis les deux versions du livre. Voir cet article de Greenlaw et Kanlabutra.

Paul Beame
la source