Ошибки в теории вычислимости

[Ales]

Отсюда $P \neq NP$ нельзя доказать контрпримером, а следовательно вряд ли возможно и более общим способом.

-- Ср фев 10, 2010 19:22:53 --

Андрей АK в сообщении #287009 писал(а):

Я тут собираю небольшую коллекцию математических ошибок

Все ошибки в коллекции принадлежат Вам.

[Xaositect]

Андрей АK в сообщении #287009 писал(а):

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

Вам никто не мешает изучать бесконечные алгоритмы.
Только правильно говорить не "Все неправильно! Теория вычислимости ошибочна!", а "Вот я тут придумал такую штуку, ИМХО это более правильный подход к теории вычислимости".

[Ales]

Почему такая постановка вопроса: "полиномиальное" время? Ведь на практике ведь нужны реальные оценки: $10^{12}$ операций или 10 секунд на Пентиуме.

-- Ср фев 10, 2010 19:35:44 --

Xaositect в сообщении #287015 писал(а):

Вам никто не мешает изучать бесконечные алгоритмы

Отсутствие предмета не препятствует его исследованию. Пустое множество еще изучать и изучать.

[Xaositect]

Ales в сообщении #287007 писал(а):

А есть ли реальные задачи сложнее чем NP?

Я вот писал про арифметику Пресбургера. Ее разрешимость сложнее. Есть еще много разных классов сложности, например, полиномиальная иерархия или $\mathbf{PSPACE}$. То, что они строго больше $\mathbf{NP}$, не доказано, но очень похоже на то, что они все-таки значительно шире.

Ales в сообщении #287007 писал(а):

Я, наверное, неправильно выразил свою следующую мысль: поскольку всегда есть быстрый алгоритм подстановки правильного ответа, нельзя доказать что $P\neq NP$. Каждая задача либо имеет, либо не имеет решения, если у нее есть решение, то есть быстрый способ проверки и алгоритм подстановки, если же Вы смогли доказать что у нее нет решения, то она тоже таким образом решена. Поэтому есть либо проблемы решенные (класса P), либо про которые ничего неизвестно (класса NP).

По-моему, Вы немного путаетесь, либо просто неправильно формулируете.
И задачи класса $\mathbf{P}$, и задачи класса $\mathbf{NP}$ - это задачи типа "да-нет".
То есть нам дано некоторое слово длины $n$, нужно определить, "хорошее" оно или нет.
В случае $\mathbf{P}$ это можно сделать за $\mathrm{poly}(n)$ шагов.
В случае $\mathbf{NP}$, если нам дадут некоторый "сертификат" того, что слово хорошее (длина сертификата - $\mathrm{poly}(n)$), то мы можем опять же за полином проверить, что этот сертификат действитель это подтверджает.
А если нам сертификата не дают, то мы можем перебрать все фозможные и проверить их. отсюда и возникает перебор и эта оценка $2^{\mathrm{poly}(n)}$

Некоторые иллюстрации:
1. $\mathbf{P}\subseteq \mathbf{NP}$. Действительно, если сертификат нам и так не нужен, мы можем просто взять его пустым.
2. $\mathrm{SAT}\in\mathbf{NP}$. Дана булева формула, определить, принимает ли она значение "истина" на некотором наборе. Сертификат - этот самый набор.
3. $\mathrm{COMPOSITES}\in\mathbf{NP}$. Определить, является ли данное число составным. Сертификат - нетривиальный делитель числа.
Недавно было доказано, что эта задача принадлежит классу $\mathbf{P}$. Сложность алгоритма, если мне не изменяет память - $n^{6+\epsilon}$

-- Ср фев 10, 2010 20:00:51 --

Ales в сообщении #287016 писал(а):

Почему такая постановка вопроса: "полиномиальное" время? Ведь на практике ведь нужны реальные оценки: операций или 10 секунд на Пентиуме.

Пентиумы развиваются слишком быстро, чтобы за ними успевать
На практике есть конкретные оценки для конкретных задач.
Вот скажем, умножение двух длинных чисел за $Cn\log n\log\log n$ операций (константу $C$, можно, конечно, оценить теоретически, но гораздо лучше определить экспериментально, тем более, что некоторые трюки, зачастую использующие особенности "железа", могут сильно ее варьировать).

А вот интересное утверждение о том, что для умножения обязательно нужно хотя бы $Cn\log n$, до сих пор не доказано. Хотя на практике оно вряд ли чем-то поможет, но, может быть, натолкнет на идеи для решения других проблем.

[Ales]

Xaositect в сообщении #287023 писал(а):

Вы немного путаетесь, либо просто неправильно формулируете

Да нет, же. Просто я непонятно написал. Я имел в виду не строгие а приближенные (в том числе и к настоящей жизни) понятия.

Иллюстрация 3 - проверка на простоту, это конечно интересная, но уже давно решенная задача.

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

Задача "да-нет" - разве не все обратные задачи сводятся к таким? Например методом деления пополам?

[Xaositect]

В общем, надеюсь, мы друг друга поняли. Вы, очевидно, больше практик, чем я.

Ales в сообщении #287028 писал(а):

Задача "да-нет" - разве не все обратные задачи сводятся к таким? Например методом деления пополам?

Сводятся, разумеется. Но там, вообще говоря, дополнительный цикл появляется, сложность может повысится.

-- Ср фев 10, 2010 20:15:14 --

Ales в сообщении #287028 писал(а):

поэтому не старался вникать в языки, сертификаты, машину Тьюринга и т.п.

Ну я писал не сильно формально, можете и почитать. Это основы, там все просто.

[Ales]

Xaositect в сообщении #287029 писал(а):

больше практик

Это вряд ли. Я просто интересовался этой задачей ($P \neq NP$).

[Xaositect]

Ales в сообщении #287031 писал(а):

Это вряд ли. Я просто интересовался этой задачей.

Ну я ей тоже интересовался. Я, собственно, во многом из-за того, что нам в 11 классе рассказали теорему Кука, решил поступать на ВМК

[Андрей АK]

Ales в сообщении #287016 писал(а):

Xaositect в сообщении #287015 писал(а):

Вам никто не мешает изучать бесконечные алгоритмы

Отсутствие предмета не препятствует его исследованию. Пустое множество еще изучать и изучать.

Вы напрасно язвите.
Бесконечные алгоритмы уже давно изучают.
Например ,в теории автоматического доказательства теорем, есть т.н. Эрбановский универсум.
Его можно назвать бесконечным алгоритмом (который к стати является алгоритмом в "моем определении" т.е. представляет собой бесконечное дерево полиномов) но который может заканчиваться за конечное число шагов.
Или другими словам - в бесконечный алгоритм подставляется конечный полином и ,в результате, получается конечный алгоритм, приводящий к доказательству некоторой теоремы.
Все рекурсивные алгоритмы - каком-то роде бесконечные.
Рекурсия - один из способов записи бесконечных алгоритмов.

[Ales]

Интересно, понятие машины Тьюринга действительно помогло при разработке компьютеров?

-- Ср фев 10, 2010 20:51:14 --

Андрей АK в сообщении #287036 писал(а):

Вы напрасно язвите.
Бесконечные алгоритмы уже давно изучают.

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

[AD]

(Оффтоп)

Ales в сообщении #287016 писал(а):

Почему такая постановка вопроса: "полиномиальное" время? Ведь на практике ведь нужны реальные оценки: $10^{12}$ операций или 10 секунд на Пентиуме.

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

Хотя, разумеется, олимпиадное программирование достаточно далеко от практики, но конкретно в этом плане как раз не очень, если, разумеется, говорить о правильном смысле слова "программирование", то есть кодинг интерфейсов на visual basic не считается.

[DiviSer]

Ales в сообщении #287010 писал(а):

Отсюда $P \neq NP$ нельзя доказать контрпримером, а следовательно вряд ли возможно и более общим способом.

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

[Ales]

DiviSer в сообщении #404678 писал(а):

Ales в сообщении #287010 писал(а):

Отсюда $P \neq NP$ нельзя доказать контрпримером, а следовательно вряд ли возможно и более общим способом.

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

Скорее философские соображения:

Предположим, что есть контрпример - задача (проверка на тавтологию для булевой функции $f(x_1,...,x_n)$) класса coNP такая, что у нас есть реальное доказательство, что она не лежит в классе P.
Значит $ f(x_1,...,x_n)=0$ не имеет решений, ведь если бы было решение, то подстановка этого решения в функцию представляло бы собой некий быстрый алгоритм, проверяющий что это не тавтология.
Но если есть доказательство, что задача не лежит в классе P, то оно одновременно является доказательством и того, что такого алгоритма не существует.
То есть, наше реальное (быстрое) доказательство того, что задача не лежит в классе P - это доказательство того, что $ f(x_1,...,x_n)$ является тавтологией. Значит мы решили задачу за быстрое время. Противоречие.

-- Ср янв 26, 2011 11:16:45 --

Замечу также, что доказательство того, что coNP не равно P не имеет практической применимости.
Для каждой конкретной задачи будет только два варианта:
1. ее можно решить быстро,
2. неизвестно, можно ли ее решить быстро.
Третий вариант, когда известно, что ее нельзя решить быстро отпадает, поскольку это означает что она все таки решена быстро.
Общее доказательство, таким образом разве что может дать существование каких-то никому не известных задач нерешаемых за быстрое время.