Problemas entre NC e P: Quantos foram resolvidos nesta lista?

20

No artigo "Um compêndio de problemas completos para P", de Greenlaw, Hoover e Ruzzo (PS) (PDF) , há uma lista de problemas em P que não são conhecidos por estarem em NC e não são completos por P . (Esta lista inclui todos os problemas em aberto na excelente pesquisa de Karp e Ramachandran .) A lista de problemas em aberto começa na página 89.

Quantos problemas desta lista foram resolvidos (por exemplo, mostrados como completos P ou NC)? Suponho que não foram resolvidos muitos nos últimos 19 anos, então isso (espero) não deve se transformar em uma grande lista.

Essa é a lista mais recente que pude encontrar. Ponteiros para uma lista mais atualizada também seriam apreciados!

EDIT: András Salamon ressalta que existe um livro dos mesmos autores com uma lista um pouco mais longa. Este é um PDF do livro. Os problemas em aberto começam na página 237.

cc.complexity-theory open-problem circuit-complexity Robin Kothari
fonte
@ Robin, por favor, CW.
Mohammad Al-Turkistany
5
@Turkistany: Como essa pergunta muito semelhante ( cstheory.stackexchange.com/q/1265/206 ) foi considerada não necessariamente CW, não tenho certeza se deve ser CWed. Vou seguir a política "Em caso de dúvida, não marque uma pergunta CW" da FAQ e aguardar mais opiniões.
Robin Kothari
@ András: Obrigado. Vou adicioná-lo ao meu post. Parece uma lista um pouco mais longa dos mesmos autores.
Robin Kothari

Respostas:

12

BTW: A lista de problemas conhecidos de conclusão do CC aumentou desde as duas versões do livro. Veja este artigo de Greenlaw e Kanlabutra.

Paul Beame
fonte