Masalah antara NC dan P: Berapa banyak yang telah diselesaikan dari daftar ini?

20

Dalam makalah "A Compendium of Problem Complete for P" oleh Greenlaw, Hoover dan Ruzzo (PS) (PDF) , ada daftar masalah dalam P yang tidak diketahui berada di NC dan tidak diketahui juga P-complete. . (Daftar ini merangkum semua masalah terbuka dalam survei yang sangat baik oleh Karp dan Ramachandran .) Daftar masalah terbuka dimulai pada halaman 89.

Berapa banyak masalah dari daftar ini yang telah diselesaikan (yaitu, terbukti P-complete atau dalam NC)? Saya kira tidak terlalu banyak yang diselesaikan dalam 19 tahun terakhir, jadi ini (semoga) tidak boleh berubah menjadi daftar besar.

Itu daftar terbaru yang bisa saya temukan. Pointer ke daftar yang lebih terkini juga akan dihargai!

EDIT: András Salamon menunjukkan bahwa ada buku teks oleh penulis yang sama yang memiliki daftar sedikit lebih panjang. Ini adalah PDF dari buku itu. Masalah terbuka dimulai pada halaman 237.

cc.complexity-theory open-problem circuit-complexity Robin Kothari
sumber
@Robin, Tolong CW.
Mohammad Al-Turkistany
5
@turkistany: Karena pertanyaan yang sangat mirip ini ( cstheory.stackexchange.com/q/1265/206 ) dianggap belum tentu CW, saya tidak yakin apakah ini harus CWed. Saya akan mengikuti kebijakan "Bila ragu, jangan tandai pertanyaan CW" di FAQ dan tunggu lebih banyak pendapat.
Robin Kothari
@ András: Terima kasih. Saya akan menambahkannya ke posting saya. Sepertinya daftar yang sedikit lebih panjang oleh penulis yang sama.
Robin Kothari

Jawaban:

12

BTW: Daftar masalah lengkap CC yang diketahui telah bertambah sejak kedua versi buku ini. Lihat makalah ini oleh Greenlaw dan Kanlabutra.

Paul Beame
sumber