Проблемы между NC и P: сколько было решено из этого списка?

20

В статье «Сборник задач, завершенных для P» Гринлоу, Гувера и Руццо (PS) (PDF) , есть список проблем в P, которые, как известно, не находятся в NC и также не известны как P-полные. , (Этот список включает все открытые проблемы в превосходном обзоре Карпа и Рамачандрана .) Список открытых проблем начинается на стр. 89.

Сколько проблем из этого списка было решено (т. Е. Показано, что они P-полные или в NC)? Я предполагаю, что не слишком много было решено за последние 19 лет, так что это (надеюсь) не должно превратиться в большой список.

Это самый последний список, который я смог найти. Также приветствуются указатели на более актуальный список!

РЕДАКТИРОВАТЬ: Андраш Саламон указывает, что есть учебник от тех же авторов, который имеет немного более длинный список. Это PDF книги. Открытые проблемы начинаются на странице 237.

cc.complexity-theory open-problem circuit-complexity Робин Котари
источник
@ Робин, пожалуйста, CW.
Мухаммед Аль-Туркистани
5
@turkistany: Поскольку этот очень похожий вопрос ( cstheory.stackexchange.com/q/1265/206 ) считался не обязательно CW, я не уверен, должен ли он быть CWed. Я собираюсь следовать политике часто задаваемых вопросов «Когда сомневаешься, не отмечать вопрос CW» и ждать большего количества мнений.
Робин Котари
@ Андрас: Спасибо. Я добавлю это в свой пост. Похоже, чуть более длинный список тех же авторов.
Робин Котари

Ответы:

12

Кстати: список известных проблем, связанных с CC, увеличился с обеих версий книги. Смотрите эту статью Гринлоу и Канлабутра.

Пол Бим
источник
10

Параллельная сложность проблемы замыкания графов (проблема , поставленная Хуллером) была решена Анджело Монти. Он показал, что проблема замыкания графа P-полна.B.1.4

Анджело Монти, О вычислительной сложности замыканий графов Письма обработки информации, том 57, выпуск 6, 25 марта 1996 года, страницы 291–295.

Мухаммед Аль-Туркистани
источник