Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 24
Спасибо, очень интересно!
В начале обещали рассказать о теоремах о невыразительности, но не рассказали :(
В начале обещали рассказать о теоремах о невыразительности, но не рассказали :(
каюсь, надо будет рассказать в следующих сериях
Автор, а в чём именно нестыковка трёх утверждений в конце?
если говорить упрощенное, то даны такие утверждения
1) A и B — эквивалентны
2) A — не может выразить задачу в P
3) B — тьюринг-полон
формальное описание по ссылкам.
Как же так эквивалентные формализмы имеют разную вычислительную сложность?
1) A и B — эквивалентны
2) A — не может выразить задачу в P
3) B — тьюринг-полон
формальное описание по ссылкам.
Как же так эквивалентные формализмы имеют разную вычислительную сложность?
3) Не понимаю, из чего следует, что логика первого порядка Тьюринг-полна.
объяснение (наверное, мне стоило поподробней расписать все утверждения):
на всякий случай, добавил в комментарии информацию о связи тьюринг полноты и слайды по логике первого порядка
на всякий случай, добавил в комментарии информацию о связи тьюринг полноты и слайды по логике первого порядка
вики о тьюринг-полноте:
In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions which compute them do not allow for an infinite loop. In the early 20th century, David Hilbert led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction which could be performed by a machine. Soon, it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved to be enough to produce every theorem by Kurt Gödel in 1930. Gödel's completeness theorem of 1930 implicitly contains a definition of a universal computer, because the logical rules acting on some axioms of arithmetic will eventually prove as a theorem the result of any computation.
The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation which deduces their theorems. Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (decision problem) was unsolvable,[1] thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique.
— формальные определения FOL можно посмотреть здесь
In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions which compute them do not allow for an infinite loop. In the early 20th century, David Hilbert led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction which could be performed by a machine. Soon, it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved to be enough to produce every theorem by Kurt Gödel in 1930. Gödel's completeness theorem of 1930 implicitly contains a definition of a universal computer, because the logical rules acting on some axioms of arithmetic will eventually prove as a theorem the result of any computation.
The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation which deduces their theorems. Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (decision problem) was unsolvable,[1] thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique.
— формальные определения FOL можно посмотреть здесь
Автору. У Вас интересная подборка, но мне кажется есть перекос в сторону рассуждений про P, NP. Вы также упорно игнорируете более универсальные методы коммутативной алгебры. Хотелось бы познакомится именно с алгоритмической составляющей. Какие идеи построения алгоритмов, в чем их преимущество и недостатки. Сложность по времени выполнения и требуемой памяти, тоже интересно, но для практики, как правило дает мало.
Некоторое философствование.
Математиков (и естественно математику) условно можно разделить на «чистых» и тех кто пытается решать конкретные задачи или стремится к этому. Есть в математике разделы про «чистые алгоритмы» там как раз и есть P, NP. Только это не к разработке алгоритмов не к их реализации никакого отношения не имеет. Это «чистая» математика. Я против нее ничего не имею. Пример «чистой» математике принесшей конкретные результаты (в криптографии) это «теория чисел» (но уже есть, хоть и слабые, квантовые компьютеры). Но это скорее исключение из правила.
Например возьмем понятие интеграла. Есть интеграл Римана и Римана — Стилтьеса, он покрывает 99% всех случаев. Есть интеграл Лебега и Лебега — Стилтьеса оставшиеся. Есть еще, не помню как называется, другое понятие интеграла. Я слушал по нему лекцию. Да интересно, он сложней формулируется, но зато много свойств проще доказывается, а некоторые вообще получаются из определения. Ну и что. Когда в тервере начинают рассуждать в крутых понятиях по интегральному исчислению, я считаю это избыточным. Сейчас полно работ по ТФКП и они говорят есть типа приложение профиль Жуковского для задачи аэрогидродинамики. Но его сто лет уже никто не использует и тем более методами ТФКП уравнение Лапласа никто не решает.
Моя интуиция говорит, что P=NP или нет нужно задавать аксиоматически и строить «чистую теорию алгоритмов» в зависимости от принятой аксиомы. Но я сомневаюсь, что на этом пути получится что-нибудь путное для практики. Например придумают «быстрый» алгоритм. которой посчитает трудную задачу за время превышающие возраст нашей Вселенной, но зато он будет из класса P, правда с очень большой константой. Вспомните, например, метод эллипсоидов (алгоритм класса P), который был предложен в 1979 году советским математиком Л. Хачияном для задачи линейного программирования.
Природу обмануть нельзя.
Некоторое философствование.
Математиков (и естественно математику) условно можно разделить на «чистых» и тех кто пытается решать конкретные задачи или стремится к этому. Есть в математике разделы про «чистые алгоритмы» там как раз и есть P, NP. Только это не к разработке алгоритмов не к их реализации никакого отношения не имеет. Это «чистая» математика. Я против нее ничего не имею. Пример «чистой» математике принесшей конкретные результаты (в криптографии) это «теория чисел» (но уже есть, хоть и слабые, квантовые компьютеры). Но это скорее исключение из правила.
Например возьмем понятие интеграла. Есть интеграл Римана и Римана — Стилтьеса, он покрывает 99% всех случаев. Есть интеграл Лебега и Лебега — Стилтьеса оставшиеся. Есть еще, не помню как называется, другое понятие интеграла. Я слушал по нему лекцию. Да интересно, он сложней формулируется, но зато много свойств проще доказывается, а некоторые вообще получаются из определения. Ну и что. Когда в тервере начинают рассуждать в крутых понятиях по интегральному исчислению, я считаю это избыточным. Сейчас полно работ по ТФКП и они говорят есть типа приложение профиль Жуковского для задачи аэрогидродинамики. Но его сто лет уже никто не использует и тем более методами ТФКП уравнение Лапласа никто не решает.
Моя интуиция говорит, что P=NP или нет нужно задавать аксиоматически и строить «чистую теорию алгоритмов» в зависимости от принятой аксиомы. Но я сомневаюсь, что на этом пути получится что-нибудь путное для практики. Например придумают «быстрый» алгоритм. которой посчитает трудную задачу за время превышающие возраст нашей Вселенной, но зато он будет из класса P, правда с очень большой константой. Вспомните, например, метод эллипсоидов (алгоритм класса P), который был предложен в 1979 году советским математиком Л. Хачияном для задачи линейного программирования.
Природу обмануть нельзя.
Очень хороший пример про метод эллипсоидов vs. simplex. Это один из примеров, где классическая теория сложности перестает помогать. Просто никто пока не понимает, почему большинство задач быстро решаются алгоритмами, которые имеют экспоненциальную асимптотическую сложность. Другой пример из статьи — SAT солверы, которые уже сейчас стали де-факто симплекс алгоритмом для NP-полных задач.
По-моему нужно уходить от worst-case и идти дальше к анализу и классификации структур проблем, как например парметеризированая сложность.
По-моему нужно уходить от worst-case и идти дальше к анализу и классификации структур проблем, как например парметеризированая сложность.
какие именно работы по «коммутативной алгебре», Вы имеете ввиду? Можно предоставить какие-нибудь ссылки на работы? Ни один из известных мне топовых SAT solver'ов (MiniSAT, SATzilla, ASP clasp, Zchaff, Ppfolio, MIPSat etc) ничем таким не пользуется.
Со стороны всегда просто рассуждать, почему одну работу ждет провал, а другую успех.
Конечно, на весь ваш список «здравого смысла» у меня (и, я уверен, у Владимира Федоровича) есть положительные ответы, но дело даже не в этом.
Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT и предлагается новый взгляд на представление этой задачи в виде структур компактных троек, который никто за 40 лет не предлагал, поэтому и нет ссылок — это новая работа, новый подход. И новая NP-полная задача. Искать сходства или различия с существующими подходами и алгоритмами — это не то, чем занимался автор.
В последней работе, на которую вы приводите ссылку, вводятся еще структуры компактных пар и метод, который лежит в основе решения доработанного алгоритма, очень схож с подходами к решению 2-SAT. Но там, например, нет никаких графов, о которых вы пишете. Вы сами-то не разобрались в этой работе, просто ссылаетесь?
Я могу понять, что у вас (и остальных) нет желания разбираться в новой статье, пока даже Романов не исследовал свой подход на практике и не опубликовал результаты. Не исследовал, в частности, потому что нет прототипа. Но его пока нет, и нет только потому, что его просто некому написать. Все действительно так просто.
Я также соглашусь, что в статье нет формального описания алгоритма. Его не было и в прошлой работе, прототип для которой был написан несколько раз. Один, последний, написал я в свое свободное время, постоянно консультируясь с Владимиром Федоровичем в течение 3-х месяцев. Видимо, с этой статьей нужно работать так же… кто возьмется пока я занят? Контакты обеспечу.
Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда. Правда, во время своей работы он нарушал теорему из статьи, чего быть, конечно, не должно. Но это ошибка в теории, которая на практике не мешала никак. Еще одной проблемой этого solver'а (точнее самого алгоритма), являлась память — ее нужно было очень (полиномиально) много — поэтому на SAT Competitions с ним делать нечего.
Новому алгоритму не нужно столько памяти, и константа в полиноме там меньше, а значит теоретически он может работать на прикладных задачах большей размерности, и может быть с ним уже можно будет пойти на SAT Competitions.
Я не могу утверждать, что новая работа 100% верна, но если новый solver будет работать качественно также как предыдущий, только быстрее и потреблять меньше памяти — это уже будет хорошо.
Конечно, на весь ваш список «здравого смысла» у меня (и, я уверен, у Владимира Федоровича) есть положительные ответы, но дело даже не в этом.
Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT и предлагается новый взгляд на представление этой задачи в виде структур компактных троек, который никто за 40 лет не предлагал, поэтому и нет ссылок — это новая работа, новый подход. И новая NP-полная задача. Искать сходства или различия с существующими подходами и алгоритмами — это не то, чем занимался автор.
В последней работе, на которую вы приводите ссылку, вводятся еще структуры компактных пар и метод, который лежит в основе решения доработанного алгоритма, очень схож с подходами к решению 2-SAT. Но там, например, нет никаких графов, о которых вы пишете. Вы сами-то не разобрались в этой работе, просто ссылаетесь?
Я могу понять, что у вас (и остальных) нет желания разбираться в новой статье, пока даже Романов не исследовал свой подход на практике и не опубликовал результаты. Не исследовал, в частности, потому что нет прототипа. Но его пока нет, и нет только потому, что его просто некому написать. Все действительно так просто.
Я также соглашусь, что в статье нет формального описания алгоритма. Его не было и в прошлой работе, прототип для которой был написан несколько раз. Один, последний, написал я в свое свободное время, постоянно консультируясь с Владимиром Федоровичем в течение 3-х месяцев. Видимо, с этой статьей нужно работать так же… кто возьмется пока я занят? Контакты обеспечу.
Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда. Правда, во время своей работы он нарушал теорему из статьи, чего быть, конечно, не должно. Но это ошибка в теории, которая на практике не мешала никак. Еще одной проблемой этого solver'а (точнее самого алгоритма), являлась память — ее нужно было очень (полиномиально) много — поэтому на SAT Competitions с ним делать нечего.
Новому алгоритму не нужно столько памяти, и константа в полиноме там меньше, а значит теоретически он может работать на прикладных задачах большей размерности, и может быть с ним уже можно будет пойти на SAT Competitions.
Я не могу утверждать, что новая работа 100% верна, но если новый solver будет работать качественно также как предыдущий, только быстрее и потреблять меньше памяти — это уже будет хорошо.
представление этой задачи в виде структур компактных троек, который никто за 40 лет не предлагал, поэтому и нет ссылок — это новая работа, новый подход. И новая NP-полная задача. Искать сходства или различия с существующими подходами и алгоритмами — это не то, чем занимался автор.
т.е. банально никто на самом деле не проверял, а не было ли предложено похожих и/или эквивалентных методов? Просто никто не будет читать работу, которая не объясняет в явной форме, чем она принципиально отличается от других: «это новая работа, новый подход.» — это не ответ. Всех интересует, чем же она действительно отличается, иначе смысл заниматься её изучением? Известно сотни NP полных задач и представлений, которые выросли из определенных задач и приложений. Весь вопрос в чем новизна подхода и представления, зачем и почему?
Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT
Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда.
Я чего-то не понимаю, но, мне кажется, эти утверждения противоречат друг другу?
т.е. банально никто на самом деле не проверял, а не было ли предложено похожих и/или эквивалентных методов?
Не могу отвечать за Романова. Я не проверял. Думаю он тоже, но это только мое мнение.
Всех интересует, чем же она действительно отличается, иначе смысл заниматься её изучением?
Ну вот вы же разобрались, чем один алгоритм отличается от другого и выше тут привели.
Или это не вы разбирались, а прочитали в статье других авторов?
Я не разбирался в чем отличие, потому что сначала надо разобраться в этом алгоритме, прежде чем его сравнивать.
А чтобы хорошо разобраться, лучше его реализовать и протестировать. Мной пока этого сделано не было.
От Владимира Федоровича я тоже не слышал этого.
Перед тем как предъявлять кому-то алгоритм решения задачи тысячелетия, АВТОР этого алгоритма должен понять и донести разницу между его алгоритмом и всеми другими попытками решить эту задачу.
В данной статье я указал, что все используемые вами структуры в принципе допускают алгебраическое представление: JSS, CSS, CTS, а значит эта ваша задача показать, что они не попадают под действие соответствующей теоремы о невыразимости.
В данной статье я указал, что все используемые вами структуры в принципе допускают алгебраическое представление: JSS, CSS, CTS, а значит эта ваша задача показать, что они не попадают под действие соответствующей теоремы о невыразимости.
Я чего-то не понимаю, но, мне кажется, эти утверждения противоречат друг другу?
В чем противоречие? Может быть я не так выразился?
Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT
эквивалентно, данная статья не даёт ответа на вопрос равенства P и NP
Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда.
в статье приводится полиномиальный алгоритм решения 3-SAT.
Верно?
Логичное и простое описание проблемы остановки с помощью диагонализатора меж тем давно на вики:
ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8
Осталось лишь сделать точное доказательство. И следовательно P != NP
ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8
Осталось лишь сделать точное доказательство. И следовательно P != NP
Это давно и строго доказано. Только P и NP не имеют отношения к этому.
Вы не правы. P и NP классы и проблема остановки тесно связаны.
Гугл вам укажет много других ссылок, я вам оставлю хотя бы одну ссылку на документ аспиранта каф. математической логики МГУ (полагаю, вполне авторитетный источник).
www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCsQFjAA&url=http%3A%2F%2Fphilosophy.ru%2Flibrary%2Fkatr%2Freferat%2Fref_computability_complexity_starikovskay.doc&ei=sAfaUq21F8b7yAP52oHIAw&usg=AFQjCNGL3sjQQuKCD-qAznXvidaCYVcKRw&sig2=5oQwES80qFUTaVZpKQxp9Q&bvm=bv.59568121,d.bGQ
Если у вас есть доказательство отсутствия связи P и NP классов и проблемы остановки — будьте добры ссылку. Подтверждайте все свои слова авторитетными ссылками пожалуйста.
Гугл вам укажет много других ссылок, я вам оставлю хотя бы одну ссылку на документ аспиранта каф. математической логики МГУ (полагаю, вполне авторитетный источник).
www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCsQFjAA&url=http%3A%2F%2Fphilosophy.ru%2Flibrary%2Fkatr%2Freferat%2Fref_computability_complexity_starikovskay.doc&ei=sAfaUq21F8b7yAP52oHIAw&usg=AFQjCNGL3sjQQuKCD-qAznXvidaCYVcKRw&sig2=5oQwES80qFUTaVZpKQxp9Q&bvm=bv.59568121,d.bGQ
Если у вас есть доказательство отсутствия связи P и NP классов и проблемы остановки — будьте добры ссылку. Подтверждайте все свои слова авторитетными ссылками пожалуйста.
Ваша очередь. Я потратил время и прочитал этот текст, и не нашел там связи между P, NP и проблемой остановки. Теперь вы сами прочитайте то, на что дали ссылку, и приведите цитату. (Хотя если вы имели в виду, что они связаны общим понятием «машина Тьюринга», то не надо).
А вот вам обоснование отсутствия связи: P и NP — это множества разрешимых задач по определению. Проблема остановки — неразрешима.
А вот вам обоснование отсутствия связи: P и NP — это множества разрешимых задач по определению. Проблема остановки — неразрешима.
Автор ведь совсем не случайно в самом конце упомянул про проблему остановки в «задачке на подумать». В том-то и суть, что эти проблемы тесно связаны.
У меня настолько много того, о чем нельзя говорить на хабре, что я, при желании, плюнул бы вам в то самое место, о котором нельзя говорить на хабре за то, что вы специально, даже по просьбе, не ставите ссылки на свои мысли.
То, что P и NP — это множества разрешимых задач, а проблема остановки — неразрешима, совсем не доказывает, что они не связаны. Это неравнозначные проблемы.
Мы с вами не эксперты в данном вопросе, поэтому предлагаю закончить обсуждение.
У меня настолько много того, о чем нельзя говорить на хабре, что я, при желании, плюнул бы вам в то самое место, о котором нельзя говорить на хабре за то, что вы специально, даже по просьбе, не ставите ссылки на свои мысли.
То, что P и NP — это множества разрешимых задач, а проблема остановки — неразрешима, совсем не доказывает, что они не связаны. Это неравнозначные проблемы.
Мы с вами не эксперты в данном вопросе, поэтому предлагаю закончить обсуждение.
Если в задаче на подумать автора заменить задачу из P на любую другую разрешимую, но невыразимую в реляционной алгебре, ничего бы не поменялось. Не в полиномиальности там дело.
Какую именно ссылку от меня вы хотите? Определение P, NP? Неразрешимость проблемы остановки? И одно, и другое очень легко гуглится, прямо на википедии. А вот вы, как подтверждение своей мысли дали ссылку, в которой ничего нет на эту тему. Вы ведь и сами видите, цитаты-то нет.
Давайте так. Если P=NP, то проблема остановки неразрешима. Если P!=NP, то то же самое. Она в принципе неразрешима, в любом случае, но это ничего не говорит о P?NP.
Более того, вопрос равенства P и NP — это вопрос различия детерминированных и недетерминированных машин Тьюринга, по определению P и NP. Но, загуглив понятие «универсальная машина Тьюринга», можно убедиться, что и детерминированные, и недетерминированные машины Тьюринга легко интерпретируются детерминированной машиной, то есть различие между P и NP исключительно в необходимом времени на работу. В проблеме остановки же необходимое время работы не фигурирует вовсе, там вопрос о возможности вычисления в принципе.
Согласен прекратить обсуждение.
Какую именно ссылку от меня вы хотите? Определение P, NP? Неразрешимость проблемы остановки? И одно, и другое очень легко гуглится, прямо на википедии. А вот вы, как подтверждение своей мысли дали ссылку, в которой ничего нет на эту тему. Вы ведь и сами видите, цитаты-то нет.
Давайте так. Если P=NP, то проблема остановки неразрешима. Если P!=NP, то то же самое. Она в принципе неразрешима, в любом случае, но это ничего не говорит о P?NP.
Более того, вопрос равенства P и NP — это вопрос различия детерминированных и недетерминированных машин Тьюринга, по определению P и NP. Но, загуглив понятие «универсальная машина Тьюринга», можно убедиться, что и детерминированные, и недетерминированные машины Тьюринга легко интерпретируются детерминированной машиной, то есть различие между P и NP исключительно в необходимом времени на работу. В проблеме остановки же необходимое время работы не фигурирует вовсе, там вопрос о возможности вычисления в принципе.
Согласен прекратить обсуждение.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Зачем нам всем нужен SAT и все эти P-NP (часть вторая)