NP≠P. Док-во от противного-контрпример алгоритмов из NP

[rubtsov_anton]

Еще раз, нет никаких алгоритмов, текстов и прочего. Есть языки и предикаты. Давайте в этих терминах.

Цитата:

Вы же и сами согласны, что "Алгоритм получения ответа для каждой конкретной задачи, разумеется должен быть", но значок "существует" не означает, что у Вас есть конкретный алгоритм, куда Вы можете подставить $x$ и даже ничего не говорит, за какое время Вы можете получить этот алгоритм.

Если именно это лежит в основе вашего доказательства, то это - банальная логическая ошибка. "Х не существует, потому что вы не можете предъявить пример Х". Если бы можно было предъявить пример алгоритма решающего задачу NP за полиномиальное время - задача была бы решена "в другую сторону". А тот факт, что никто такого алгоритма предъявить не может - не доказательство неравенства классов, а констатация факта. Для того, чтобы доказать их неравенство, нужно именно победить это неконструктивное существование $R_p$.

[dmitgu]

rubtsov_anton в сообщении #873303 писал(а):

Еще раз, нет никаких алгоритмов, текстов и прочего. Есть языки и предикаты. Давайте в этих терминах.

Цитата:

Вы же и сами согласны, что "Алгоритм получения ответа для каждой конкретной задачи, разумеется должен быть", но значок "существует" не означает, что у Вас есть конкретный алгоритм, куда Вы можете подставить $x$ и даже ничего не говорит, за какое время Вы можете получить этот алгоритм.

Если именно это лежит в основе вашего доказательства, то это - банальная логическая ошибка. "Х не существует, потому что вы не можете предъявить пример Х". Если бы можно было предъявить пример алгоритма решающего задачу NP за полиномиальное время - задача была бы решена "в другую сторону". А тот факт, что никто такого алгоритма предъявить не может - не доказательство неравенства классов, а констатация факта. Для того, чтобы доказать их неравенство, нужно именно победить это неконструктивное существование $R_p$.

Побеждать неконструктивное существование можно и для варианта $\exists R(\widehat{L(y,x)}, x)$, но этот вариант показывает полиномиальность времени получения решающего алгоритма, а в Вашем определении этого никак не видно.

Что же касается того, в каких терминах обсуждать - то это дело вкуса. Потому что доказана эквивалентность и машин Тьюринга, и рекурсивных функций, и аббака и не только. Мне нравится рассуждать в терминах алгоритмов и их текстов - просто потому что это близко к "номерам Геделя" - в принципе, аналог тех же текстов. Ну и близко к практически знакомому многим программированию. Но опять же - это дело вкуса.

[rubtsov_anton]

А почему это должно быть видно? Ведь смысл именно в том чтобы доказать неверность именно утверждения $P=NP$, а не более сильного.

Цитата:

Что же касается того, в каких терминах обсуждать - то это дело вкуса.

Разумеется. НО! Критически важно выбрать набор терминов, в которых ведется обсуждение, и не выходить за его пределы. Если хотите рассуждать в терминах алгоритмов, не втаскивайте в обсуждение языки и предикаты, и наоборот.

[dmitgu]

rubtsov_anton в сообщении #873317 писал(а):

А почему это должно быть видно? Ведь смысл именно в том чтобы доказать неверность именно утверждения $P=NP$, а не более сильного.

Цитата:

Что же касается того, в каких терминах обсуждать - то это дело вкуса.

Разумеется. НО! Критически важно выбрать набор терминов, в которых ведется обсуждение, и не выходить за его пределы. Если хотите рассуждать в терминах алгоритмов, не втаскивайте в обсуждение языки и предикаты, и наоборот.

У нас с Вами разное представление о $P=NP$. О каком равенстве можно говорить, если, например, переход от $L(x, y)$ к $R(x)$ оказывается неполиномиальным относительно размера текста алгоритма $L(x, y)$? Это важное свойство, которое может оказаться существенным при построении доказательства. И выкидывать существенные свойства - это ухудшать свои возможности по поиску решений.

Что же касается выбора круга терминов - то я и не выхожу за пределы. Просто под $L(x, y)$ к $R(x)$ я понимаю именно алгоритмы.

[rubtsov_anton]

Ну, у меня стандартное представление о равенстве.
Я беру определение для языка или задачи, которые входят в NP, беру определение языка или задачи, которые входят в P и строю равенство как утверждение вида:

Для любой задачи(языка) из класса NP эта задача является задачей(языком) класса P.

Это прямо определение равенства двух множеств. "Множества А и Б - равны, если А входит в Б, а Б входит в А".
А вхождение определяется как "А входит в множество Б, если каждый элемент принадлежащий А принадлежит и Б"

Обратное вхождение (т.е. вхождение всех задач класса P в класс NP) является тривиальным.

Любое другое определение равенства классов требует доказательства эквивалентности с указанным.

[dmitgu]

rubtsov_anton в сообщении #873333 писал(а):

Ну, у меня стандартное представление о равенстве.
Я беру определение для языка или задачи, которые входят в NP, беру определение языка или задачи, которые входят в P и строю равенство как утверждение вида:

Для любой задачи(языка) из класса NP эта задача является задачей(языком) класса P.

А как Вам такая задача из NP: по тексту $L_{p_1}(y, x)$ найти текст $R_{p_2}(x)$ ?
Разве ее не требуется решать в случае поиска равенства этих классов? Я думаю - приходится. Поэтому и добавляю ее внутрь своего определения.

[rubtsov_anton]

Сформулируйте задачу полностью и докажите её принадлежность классу NP.

[dmitgu]

rubtsov_anton в сообщении #873352 писал(а):

Сформулируйте задачу полностью и докажите её принадлежность классу NP.

Я не буду этого делать. Потому что это должно входить в определение. Потому что с точки зрения расчета принципиальной разницы между размером $x$ и размером $L$ нет. Одно может переходить в другое кстати (слово может быть набором параметров, некоторые могут подставляться). И если у нас экспоненциальная зависимость поиска $R$ от текста $L$, то для небольшого размера $L$ нас уже не будет интересовать "существует" ли соответствующий $R$, потому что его поиск будет неприемлемо трудной для расчета задачей. Поэтому я и формулирую определение так, как формулирую. Давайте дождемся мнения стороннего наблюдателя. Если интересно.

Но вобще спор несколько излишний, потому что если есть решение $NP = P$, то есть решение для $NP$-полной задачи, а переход от нее к любой другой - полиномиален. Поэтому мое определение вполне допустимо даже для Ваших "усеченных" (по сравнению с моими) требований, имхо.

[rubtsov_anton]

Вопрос в том, что вы подразумеваете под этими L, R и x?

[dmitgu]

rubtsov_anton в сообщении #873365 писал(а):

Вопрос в том, что вы подразумеваете под этими L, R и x?

Даже не знаю как это объяснить. Шучу. Мне тут надо еще к работе кое-что сделать, может позже дообсуждаем, если интерес сохранится и нам тут все не разъяснят. Доброго вечера.

[rubtsov_anton]

С добрым утром. :) Я готов продолжать обсуждение.

[dmitgu]

rubtsov_anton в сообщении #873541 писал(а):

С добрым утром. :) Я готов продолжать обсуждение.

Доброе утро, Антон.
Вы согласны, что необходимое условие для $NP = P$ является существование текста для алгоритма- решения одной (неважно какой) из полиномиально полных задач?
$\exists \widehat{R_{L_0}(x)}$

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

Это как раз то необходимое условие, которое я опровергаю при опровержении $NP = P$. Потому что опровержение необходимого условия для $NP = P$ означает опровержение и самого $NP = P$.

Счас на работу иду, наверно не отвечу. Но вроде вопрос и так ясен.

[Xaositect]

dmitgu в сообщении #873869 писал(а):

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

Это неправда. Существует алгоритм, получающий доказательство того, что задача лежит в $\mathrm{NP}$, и выдающий полиномиальный алгоритм ее решения.

[rubtsov_anton]

dmitgu в сообщении #873869 писал(а):

Вы согласны, что необходимое условие для $NP = P$ является существование текста для алгоритма- решения одной (неважно какой) из полиномиально полных задач?

Должна существовать детерминированная машина Тьюринга, решающая одну из NP-полных задач за полиномиальное время. Вы, вроде, это имели в виду.

dmitgu в сообщении #873869 писал(а):

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

Тривиально следует, что есть процедура вида

for problem in NP:
  if input == problem:
    return Result[problem]

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

Существование алгоритма, который можно запрограммировать - нетривиально и требует доказательства. Разумеется, отсутствие машины Тьюринга, которая бы решала данную задачу выводит саму задачу за рамки класса NP.

[Deggial]

rubtsov_anton, обратите внимание на оформление цитат. Цитирование делается с помощью кнопок и . Для работы кнопки "Вставка" требуется выделить цитируемую часть сообщения и нажать кнопку именно в данном сообщении. Всё это нужно для того, чтобы было видно, кого Вы цитируете и чтобы была ссылка на цитируемое сообщение - последнее крайне желательно.

И ещё: просьба воздерживаться от постов типа

rubtsov_anton в сообщении #873541 писал(а):

С добрым утром. :) Я готов продолжать обсуждение.

которые по существу являются бессодержательными.