Интервью с Кнутом, 20 вопросов. Оказывается, он думает что P=NP maybe.
Дальше, из этой теоремы следует что любое множество графов хорошо упорядочено — содержит не более конечного числа минимальных графов.Что тут минимальный граф? Граф из этого множества, у которого ни один минор не принадлежит этому множеству? Не исчезает ли тут вычислительный конструктивизм, то есть это (и следующее ниже) утверждение говорит лишь о существовании или же о способе нахождения? Свойство множества типа well-quasi-ordering хорошо для доказательства существования конечного числа минимальных элементов, но я что-то просмотрел способ, как практически перебрать всё бесконечное множество, пусть оно и хорошо квази-упорядоченное.
Далее, для любого замкнутого множества графов, т.е. где взятие минора от графа даёт граф принадлежащий множеству, ну например планарные графы, существует конечное количество запрещённых миноров (минимумов комплементарного множества которое полностью определяет наше множество. Для планарных графов это полный граф из четырёх вершин плюс граф из 3 + 3 попарно соединённые.Бессмысленно попридираюсь, ты имел ввиду полный граф из 5 вершин.
Это уже WTF дичайше.
Ну типа определяем бесконечное множество графов, с единственным ограничением что оно должно быть замкнутым под операцией взятия минора (и даже, как я понимаю, не обязательно строго минора через один шаг и всё, наше множество определено конечным количеством запрещённых графов из которых мы бы могли в него попасть из комплементарного множества. ОМГ.А что тут такого удивительного? Множество же примеров как бесконечные множества описываются конечным числом генераторов/образующих и т.д. Как это помогает в вычислительном плане?
P.S. я в теории графов/комбинаторике/алгоритмах лох, интервью не смотрел, так что скорее всего чего-то не догнал, что такое 3SAT — ХЗ, почитаю.
> 3SAT решается через это. Что вот, пре-вычислите более-чем-астрономическое количество графов, тогда у вас есть полиномиальный олгоритм где константа это количество запрещённых миноров.
А как 3SAT сводится задачам на графах и относительно какой операции искомое множество замкнуто?
А как 3SAT сводится задачам на графах и относительно какой операции искомое множество замкнуто?
Не исчезает ли тут вычислительный конструктивизмВ том-то весь и понт, что исчезает!
Эта офигенная теорема как бы указывает на интересную loophole в понятии вычислимости.
С одной стороны, как я сказал, любое конечное число вычисляемо алгоритмом который его печатает. То есть вот эта теорема говорит что для конкретного множества графов замкнутого по взятию минора есть какое-то конкретное число запрещённых миноров которое полностью описывает это множество и позволяет полиномиально (с количеством тех миноров вынесенным в константу) проверять принадлежность. Всё вычислимо и даже эффективно вычислимо.
С другой стороны, как бы нет (и, прозреваю, не может быть вычислимого) алгоритма который тебе скажет сколько именно запрещённых миноров тебе нужно найти для произвольного такого множества графов. Ну вот нашёл ты 127, а потом долго не находил ни одного ещё, дальше что? Если ты засунешь их в первый алгоритм, то зашибись, он будет работать, но не факт что корректно, вдруг там есть ещё 128-ой запрещённый минор который твоим перебором не найдётся до тепловой смерти вселенной? А вдруг и 129-ый тоже есть?
Я потому и офигеваю с этого всего, что удивительно же. Оказывается, что алгоритмы допускают разделение на preprocessing and processing, и все наши понятия (эффективной) вычислимости как бы относятся к processing, как бы игноририруя preprocessing (ну, достаточно доказать _существование_ алгоритма с кучей preprocessed инфы а вот тут оказывается что можно показать что алгоритм существует, но как бы неконструктивно, причём более неконструктивно чем "препроцессинг будет долгим", он может быть вообще невычислимым (для класса алгоритмов, не для конкретного одного — но твой алгоритм препроцессинга как бы будет работать с классом алгоритмов).
@__SS__: "А как 3SAT сводится задачам на графах и относительно какой операции искомое множество замкнуто?" — если б я знал, я б пошёл за своим миллионом баксов. Я говорю что это выглядит не особенно невозможным.
> Эта офигенная теорема как бы указывает на интересную loophole в понятии вычислимости.
С учётом того, что таких множеств очень мало (счётно может, принадлежность к этим множествам и без запрещающих миноров полиномиально вычислима?
С учётом того, что таких множеств очень мало (счётно может, принадлежность к этим множествам и без запрещающих миноров полиномиально вычислима?
С учётом того, что таких множеств очень мало (счётно)что
Мы как бы тут вообще только со счётными множествами работаем. Вообще всегда.
"Есть задачи, для которых можно доказать существование эффективного алгоритма, но при этом нельзя этот алгоритм построить."
Это имелось в виду? Честно говоря, это не кажется удивительным.
Это имелось в виду? Честно говоря, это не кажется удивительным.
а так тупо смотрим для каждого из них не минор ли он у нашего графа (за О(n^3) вершин нашего графа).Это не ясно, как делать. Я не знаю даже, как проверить за О(n^3 не является ли данный граф подграфом нашего графа. А нам еще надо проверить, не является ли подграфом нашего графа что-нибудь гомеоморфное.
> Это не ясно, как делать.
http://en.wikipedia.org/wiki/Graph_minor#Algorithms (я не читал сам алгоритм, правда).
http://en.wikipedia.org/wiki/Graph_minor#Algorithms (я не читал сам алгоритм, правда).
Оставить комментарий
bleyman
http://www.informit.com/articles/article.aspx?p=2213858&... — интервью, собственно.Кроме топика меня порадовал ответ на вопрос номер 18, оказывается, KMP был им стырен у автоматического генератора автоматов, когда он смог просечь как оно так быстро работает.
Но! Вопрос про P?=NP, номер 17, содержит ссылку на мозговыносящую теорему http://en.wikipedia.org/wiki/Robertson%96Seymour_theorem
Сама по себе она довольно вменяемая, говорит что нельзя построить бесконечное множество ненаправленных графов, в котором никакие два графа сравнимы друг с другом по принципу is a minor of (то есть что один можно получить из другого удалением вершин, рёбер, или сливанием вершин, короче "подграф" на максимальных стероидах).
Дико интересно могу ли я где-нибудь её найти и понять, но и так вроде не вызывает отторжения: ну, прикинь, пытаюсь я строить это бесконечное множество и начинаю с графа из одной ноды. Упс, больше нет, все остальные графы содержат его как минор. Ок, давай начну с двух нод — та же фигня. С треугольника — все остальные графы должны быть деревьями. Можно начать с кучи графов с миллионом вершин, но я как бы верю что чуваки доказали, что каждый раз когда ты включаешь какой-то граф в своё множество, ты слишком много бОльших графов у которых он минор исключаешь.
Дальше, из этой теоремы следует что любое множество графов хорошо упорядочено — содержит не более конечного числа минимальных графов. То есть берёшь любой элемент, идёшь вниз по минорам как угодно, заканчиваешь в одном из конечного числа минимальных графов. Это уже ой-ой-ой. (первое: у нас не может быть бесконечной убывающей последовательности (сумма количества вершин и рёбер убывает и не может быть меньше нуля второе: если б у нас было бесконечное количество минимумов, мы бы построили то множество несравнимых графов которое не существует).
Далее, для любого замкнутого множества графов, т.е. где взятие минора от графа даёт граф принадлежащий множеству, ну например планарные графы, существует конечное количество запрещённых миноров (минимумов комплементарного множества которое полностью определяет наше множество. Для планарных графов это полный граф из четырёх вершин плюс граф из 3 + 3 попарно соединённые.
Это уже WTF дичайше. Ну типа определяем бесконечное множество графов, с единственным ограничением что оно должно быть замкнутым под операцией взятия минора (и даже, как я понимаю, не обязательно строго минора через один шаг и всё, наше множество определено конечным количеством запрещённых графов из которых мы бы могли в него попасть из комплементарного множества. ОМГ.
Более того, количество запрещённых графов имеет тенденцию взрываться супер-экспоненциально: зацените вот эту хрень: http://en.wikipedia.org/wiki/Petersen_family — простое определение "графа без хитровыебнутых циклов" через очевидные операции: заменить треугольник на вершину, и наоборот, и поудалять висящие вершины и позаменять вершины с двумя рёбрами на просто ребро (всё из анализа электрических цепей, между прочим! Так что физики, это про вас!) даёт пиздецеобразное количество запрещающих миноров для тривиальных цепей (которые сводятся к одной вершине) в 68,897,913,652 как минимум.
Чё Кнут не говорит но, как я понимаю, думает, легко может быть ситуация что например 3SAT решается через это. Что вот, пре-вычислите более-чем-астрономическое количество графов, тогда у вас есть полиномиальный олгоритм где константа это количество запрещённых миноров, а так тупо смотрим для каждого из них не минор ли он у нашего графа (за О(n^3) вершин нашего графа).
Ещё более смешно то, что как я понимаю процедура пре-вычисления может оказаться и вовсе uncomputable (для произвольного определения перехода к минору ну, как ты узнаешь что ты их все вычислил? Но для конкретного определения перехода к минору нужного для 3SAT, хуле, вот теорема что конечное количество минимумов, так что решаемо, лол. Любое конечное число вычисляемо алгоритмом который его печатает. А вот в общем смысле вычислить нельзя, ни реально, ни в принципе, а так P=NP.
Меня это как-то аж заколдобило, я внезапно понял, что P=NP это реально возможная ситуация. Алсо, дико пропёрся с теоремы про графы, красава же!