Посмотрел по диагонали; неинтересно.
Не понял, почему он связывает P/NP именно с аксиомой выбора; гораздо естественнее аналогия с борелевскими/проективными множествами. Я даже одно время верил, что эту связь можно уточнить настолько, что удастся доказать P#NP, но потом, слава богу, разуверился.

(Reply to this) (Thread)

Именно так, неинтересно и пусто.

А в чем аналогия с борелевскими множествами ? Почему аналогия с АС не только ради красного словца, я не вижу.

(Reply to this) (Parent) (Thread)

На примере проблемы изоморфизма графов (про которую, кстати, не доказана НП-полнота).
На входе - две матрицы смежности; надо узнать, изоморфны ли графы. Задача в НП, потому что множество входов с ответом "да" - проекция множества, принадлежность к которому проверяется коротким (полиномиальным) перебором. А именно, пара матриц смежности плюс биекция между вершинами, задающая изоморфизм. Чтобы проверить, надо проверить, что это биекция, и что она сохраняет смежность-несмежность. (При проецировании просто исчезает информация о биекции).

А если графы счетны, то аналогом "легко проверяемого" множества служит борелевское: построимое за счетное число простых шагов. Проекция к "простым" шагам не относится; проекции борелевских множеств - уже более сложные, проективные. В частности, доказано, что множество пар изоморфных счетных графов - не борелевское, хотя очевидным образом есть проекция борелевского.

А вот чего я не знаю (может, просто лень разузнать) - это для какого счетного графа множество всех, ему изоморфных, - не борелевское.

Вот такие мутные размышления. Еще можно спросить french_man@ljа, он когда-то рассказывал здесь о "теории классификации".

(Reply to this) (Parent)