Comments | baaltii1: Интервью Владимира Воеводского (часть 1)

baaltii1

Интервью Владимира Воеводского (часть 1)

Jul 01, 2012 09:13

Это интервью математика Владимира Воеводского. Обычно в интервью ученых касаются формальных сторон их деятельности, примерно того, что и без всяких вопросов-ответов ясно, а то, что на самом деле интересно и важно, остается скрытым. Владимир Воеводский - лауреат медали Филдса, профессор Института Высших Исследований в Принстоне, создатель мотивной ( Read more... )

Leave a comment

Back to all threads

vividha July 3 2012, 13:57:01 UTC

Это не так. Основная проблема была в том чтобы найти новый язык на котором можно формально работать с объектами с которыми работает современная чистая математика. Теория множеств для этого не годится, грубо говоря по тому что на ее языке комбинаторная сложность описания объектов растет экспоненциально с ростом уровня абстрактности.

dimpas July 3 2012, 14:09:30 UTC

тем не менее первая из 4 тем в
http://www.math.ias.edu/sp/univalent/goals
прикладная, да и вторая тема, в общем, довольно типичный TCS.

ну а если Ваша "Основная проблема" решится положительно, то не получится ли из нее P=NP?

vividha July 3 2012, 14:17:29 UTC

Все правильно, безусловно прикладная компонента здесь есть и она, особенно на сегодняшнем этапе, важна. Просто не правильно считать что ей все и ограничивается.

Что касается P и NP то я прямых связей с тем что я делаю не вижу.

dimpas July 3 2012, 14:32:30 UTC

Что касается P и NP то я прямых связей с тем что я делаю не вижу.
просто ваша "проблема" прозвучала как желание свернуть последовательность из k перемежающихся кванторов в формуле в константное их количество...

я вообще не понимаю разделения математики на чистую и прикладную, честно говоря (только на плохую и хорошую) :-)
Может быть потому, что одно из моих занятий - применение прикладной математики (нелинейной и линейной оптимизации) в чистой.

vividha July 3 2012, 14:38:01 UTC

Тут более разумная аналогия такая. Теория множеств и унивалентные основания это два способа "кодирования" одной и той же информации. Например натуральное число можно записать как длинную сумму единиц а можно в двоичной или десятичной записи. Разница в сложности экспоненциальная.

dimpas July 3 2012, 14:42:39 UTC

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

vividha July 3 2012, 14:51:34 UTC

Быть такого не может, потому что перевести бинарную запись в сумму единичек занимает почти столько же времени сколько просто прочесть эту последовательность единичек (что то вроде C*log(N)*N по сравнению с N ).

dimpas July 3 2012, 15:01:55 UTC

может, и еще как. Классическая задача такого типа: knapsack.

У нас есть, грубо говоря, система из двух линейых диофантовых уравнений,
которая решается (в классической вычислительной модели, стандартным динамическим программированием) за время, пропорциональнальное полиному от числа переменных и максимума W абс. значений коэффициентов. Заметим, не от log(W), a именно от W.
A задача NP-полна (т.е. коэффициенты должны быть немаленькие, чтоб такого добиться).

nikaan July 11 2012, 06:49:44 UTC

о, а Вы не знаете, почему в задаче о рюкзаке - и похожих - помогают генетические алгориты? Я над этим думал, сколько-то объяснений придумал, но они плохие

dimpas July 11 2012, 07:05:23 UTC

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

Но, насколько я знаю, для генетических алгоритмов такого никто не делал. Да и это выглядит дико трудным.
Уже за такие гораздо более простые штуки, как анализ "в среднем" симплекс-метода для линейного программирования, люди получают премии (Nevanlinna Prize) и т д, см
например
http://gilkalai.files.wordpress.com/2010/08/dsicm10.pdf

Вообще-то генетические алгоритмы, похоже, выродились в некий культ, под-область типа "черная дыра", откуда никакого света никому давно нету, ИМХО...

nikaan July 11 2012, 07:32:10 UTC

не, ну вопрос ясный, генетические алгоритмы для наугад взятой задаче о рюкзаке хорошо работают. почему? )) просто я с ними много работал, и сейчас тоже, и удивляюсь. Я искал в инете объяснения, есть какие-то книжки, но там фигня какая-то

dimpas July 11 2012, 07:56:49 UTC

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

А так, возьмите достаточно приличный integer linear programming solver, скажем, CPLEX, и попробуйте его побить вашей генетической эвристикой...

nikaan July 11 2012, 21:11:59 UTC

нене, я немного по-другому формулирую. Вот есть энмерный куб из нулей и единиц, там какую-то функцию надо оптимизировать (ну там выпуклую, с небольшими проихводными, не знаю) - типа как в задаче о рюкзаке. Разрешается применять локальный эвристики (типа в шарике какого-то константного радиуса брать точку со значением функции побольше). Понятно, что так почти никогда околомаксимальные значения функции не найдутся. А если брать генетическую идею - скрещивать локальные максимумы, то найдётся. То есть есть какая-то структура на локальных максимумах. И вот непонятно, что за структура.

dimpas July 13 2012, 12:49:57 UTC

это, однако, совсем другая наука, к рюкзаку не имеющая прямого отношения. Это скорее про оптимизацию субмодулярных функций. Про это есть особая индустрия...
погуглите Submodular_set_function

cadadr July 4 2012, 01:12:30 UTC

Но сложность считается как функция от длины входной последовательности. Так что если на входе есть числа в унарной записи, то задачу в этом смысле решить может быть сильно проще, чем если бы они были в бинарной записи. Известно много задач, которые решаются за полиномиальное время от некоторых параметров, но для которых не известно алгоритма, полиномиального от длины этих параметров (например, в бинарной записи).

Связь с P vs. NP и подобным может легко проявиться. Скажем, к определенной вычислительной задаче про proof assistant может сводиться известная задача из какого-нибудь сложного класса (может даже не NP, а сложнее). Тогда эффективное решение задачи для proof assistant'а будет, вообще говоря, означать схлопывание каких-то классов сложности.

vividha July 4 2012, 10:10:40 UTC

Тут просто путаница. Я говорил не о сложности вычислений как функции от объема ввода а о сложности т.е. объеме объекта получающегося в результате кодирования одной и той же информации различными способами.

Математическое определение можно закодировать на языке теории множеств а можно на языке унивалентных оснований. Все что я пытался сказать это то что для абстрактных определений первое может быть экспоненциально длиннее второго.

Back to all threads