dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

Задачи из NP - проверять только «слова» или ещё и «дела»?

Копирую сюда свой пост с dxdy.ru - http://dxdy.ru/post960183.html#p960183

Про класс NP и про NP_primitive.

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

Так вот вопрос - а если в теории (а моя задача теперь будет вполне конкретная математическая теория) я аксиоматизирую, чему должен быть равен алгоритм решения Mt когда он разбирается с алгоритмом AntiMt()? Притом аксиоматизирую корректно:

Mt(Aks, «AntiMt()») = knockout

И в составе аксиом Aks будет находится и само это равенство (я это сделаю при помощи диагонализации). Разве это не докажет моментально неполноту алгоритма решения Mt и невозможность, таким образом, свести задачу к задаче класса P?

Я поясню. Эта аксиома вместе с прочими оказывается непротиворечивой, если Mt(Aks, «AntiMt()») действительно выдаст knockout (довольно очевидно, но докажу). Но тогда алгоритм Mt неполный, потому что он ничего не выдает про поведение AntiMt(). В то время как в теории результат для AntiMt() выводится из данной аксиомы.

Разумеется, Mt(Aks, «AntiMt()») может вопреки аксиоме выдать «правильный» прогноз для AntiMt() - соответствующий короткому доказательству из новой аксиомы. Да только этот результат будет неправильным - потому что AntiMt() всегда опровергает предсказания Mt (кроме случая когда Mt ничего не прогнозирует и выдаёт knockout). И сама теория будет противоречивой, разумеется! И вот что интересно. Нам же алгоритм решения Mt нужен для того, чтобы получать решения. Правильные. И если мы получаем то, что не отвечает теории, то мы отвергаем такой алгоритм решения.

Но в данном случае «обманывающий» Mt явно не отвечает теории - он поступает вопреки аксиоме Mt(Aks, «AntiMt()») = knockout для того, чтобы «спрогнозировать» AntiMt(). Вот если бы он выдал результат, расходящийся с логическим выводом, то мы бы признали алгоритм ошибочным? Да. И нас бы не остановила разница во времени работы проверки доказательства и его поиска. Это касается подстановки текстов алгоритмов в качестве аргумента в Mt.

Хорошо, а на саму работу алгоритма мы смотрим или нет? Если его собственный результат расходится с аксиомой, например? Да и по факты тут это неизбежно приводит к противоречию и расхождению с реальностью (противоречием теории). А по времени на сравнение - тут не больше, чем сравнивать работу Mt(Aks, «AntiMt()») как прогнозиста для AntiMt(), либо сравнивать работу Mt(Aks, «AntiMt()») с аксимой про сам Mt. Второй случай даже быстрее, потому что результат для AntiMt() надо ещё вывести (будет Anti(knockout) - если посмотрите в прошлое доказательство).

Мне кажется, что есть все основания смотреть и заявлять о некорректности алгоритма, если его поведения расходится с теорией. Прогноз от алгоритма - это «слова», а его собственное поведение - это «дела», фигурально выражаясь. Дела не менее важны , чем слова, а для корректности - так и более.

Просто возникают интересные эффекты, когда мы находимся в столь сложной задаче, которая в состоянии выражать любое решение (алгоритм). Странно, почему раньше никто подробно не рассматривал в качестве задачи из NP математическую теорию. По крайней мере я не видел. А для таких дел ведь много наработок в логике.

В принципе я обозначил всё доказательство - поставить аксиому Mt(Aks, «AntiMt()») = knockout как расширение теории Пеано, показать непротиворечивость при корректной работе Mt и - неполноту в силу этого. Ну и очевидная некорректность (противоречивость теории и ложные результаты) при «правильном» прогнозе для AntiMt(). Правильном только по короткому доказательству, но не по факту работы - который тоже можно отразить в доказательстве.

Всё это я привел ниже, но проблема ясна и так, поэтому формальное доказательство ниже я привожу просто для аккуратности.

Предварительно скажу кое-что про «окрестности» проблемы. Очень похоже (вообще я уверен, но мало ли...), что в теории алгоритмов есть парадокс (попросту ошибка), когда математики ставят состав математического объекта (класс задач NP) в зависимость от своих знаний. Об этом я писал в предварительном эвристическом варианте ( http://dxdy.ru/post954742.html#p954742 ). Суть в том, что они хотят, чтоб туда входили лишь задачи, чей алгоритм проверки они знают. Хотя есть задачи, чей алгоритм проверки удовлетворяет требованиям класса NP, но какой это алгоритм - решения в общем случае нет. И приведенное ранее (перед этим) мое доказательство для NPP (постановка задачи - http://dxdy.ru/post956171.html#p956171 , доказательство - http://dxdy.ru/post956292.html#p956292 ) существенно опирается на невозможность решить вопрос - какой там реально алгоритм в общем случае.

Но - вообще-то - есть и задачи из класса NP, чей алгоритм проверки действительно известен, либо который можно легко найти в общем случае. И для этого частного случая требуется отдельное доказательство, что этот NP_primitive (назову так этот «псевдоподкласс» в NP) тоже не сводится к P.

Я бы назвал такие задачи «задачами с известным полиномиальным алгоритмом проверки», но так нельзя определять математические объекты, потому что вопрос - кому известный? Институту им. Стеклова, водопроводчику Фёдору или, например, межгалактической академии инопланетян? Может, правильно говорить о таких множествах задач из NP, которые объединены друг с другом заранее заданным алгоритмом проверки некоторой «основной» задачи и заранее заданной сводимостью к ней остальных задач (если в определяемом множестве больше, чем одна задача)? И подобное множество будет тогда не единственным, видимо. Но, вопрос с определением довольно тонкий, и предмет коллективного обсуждения.

Это к вопросу о терминах. Пока мне не объяснили где у меня ошибка, я все же предпочел бы пользоваться обозначением NP_primitive для задач из класса NP с заранее заданным алгоритмом проверки.

Мое предыдущее доказательство не позволяет, например, дать ответ о (не)сводимости задачи выполнимости ДНФ (дизъюнктивной нормальной формы - уравнению из булевых переменных) к задаче из класса P. А ведь такой вопрос имеется.

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

Постановка задачи

1. Имеется некоторая система аксиом Aks (пусть непротиворечивая), расширяющая теорию Пеано. Эти аксиомы заданы некоторым списком (можно считать для начала что список расширения пуст). В качестве элементов списка стоят аксиомы или схемы аксиом (пример схемы аксиом - любая аксиома логики - там используются формульные переменные). И у нас есть быстрый способ добавления в любой такой список новой аксиомы - после чего  получается новый список аксиом с теми же свойствами списка. Способ добавления аксиомы обозначим как AddAks(Aks, X) - в результате работы этот алгоритм вернет список аксиом Aks, расширенный аксиомой X. Иногда для простоты я буду писать Aks + X вместо приведенной формулы - когда ясно, что речь об аксиомах.

2. В качестве проверяемого слова будем рассматривать пару текстов - список аксиом из п. 1 и A() – записанный на языке теории текст алгоритма.

3. В качестве слова-свидетеля будем рассматривать текст доказательства для A() = i. Где i – некоторое число (можно считать, что число записано в десятичном представлении, но тут это не принципиально). Если имеется слово x и слово-свидетель y, то, как известно из логики, можно при помощи алгоритма автоматической проверки доказательств R(Aks, x, y) за полиномиальное время (число шагов) Py(|y|+|Aks|) от размеров y и Aks проверить, доказывает ли y какое-то равенство A() = i для x на базе аксиом Пеано, расширенных аксиомами Aks. На размер y накладывается стандартное для NP ограничение некоторым полиномом Px(|x|). Разумеется, если в качестве x и/или y и/или Aks выступает какой-то бессмысленный текст, то R(Aks, x, y) возвращает «ложь».

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

Берем нашу задачу из пунктов 1-3. Берем метод поиска слов-свидетелей y, подходящих для заданного слова  x (то есть, |y| < Px(|x|) и R(Aks, x, y) дает истину). Назовем наш метод поиска слов-свидетелей для  слова  x - алгоритмом Mt(Aks, x).

Для простоты считаем, что Mt(Aks, x) выдает не текст доказательства (слово-свидетель), а результат этого доказательства (число i в некотором представлении) как прогноз результата работы алгоритма A(). Напомню, что текст некоторого алгоритма A() подставлен на место переменной x, когда решается вопрос про результат работы этого алгоритма.

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

Если же нужного доказательства среди подходящих по размеру доказательств ему найти не удалось, то Mt(Aks, x) возвращает knockout. Ясно, что результаты Mt не прямо равны результатам A() - просто потому, что результаты могут быть какие угодно, а нам надо еще занять место для knockout, который ведь тоже может выдаваться какими-то алгоритмами. Есть разные способы ставить значения в соответствие друг другу, например - канторова пара из признака 1 и результата работы A(), либо просто 0 и 0 - для knockout.

Просто введем следующее обозначение для соответствия результатов самих алгоритмов и результатов прогнозов для них от Mt:

Если A() = i, и Mt(Aks, «A()») выдает правильный прогноз, то Mt(Aks, «A()») = FormatMt(i).

Разумеется, FormatMt(i) обратим - то есть, по нему можно узнать i. И FormatMt(i) никогда не возвращает knockout.

И, разумеется, время (количество шагов ) работы Mt(Aks, x) конечно и ограничено некоторым всюду определённым полиномом T(|Aks| + |x|).

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

Если такого Mt не существует, то NP_primitiveP. Мы будем доказывать «от противного» и поэтому работаем, словно Mt в нашем распоряжении.

Если же для какого-то проверяемого слова Mt выдаст результат knockout, хотя подтверждающее слово-свидетель есть, то алгоритм Mt будем называть не полным.

Если же Mt выдал значимый результат (не knockout) для проверяемого слова, которое не имеет подтверждающего его слова-свидетеля, то Mt будем называть не корректным.

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

Существует ли хоть один корректный Mt? Да - который всегда возвращает knockout, например.

Чтобы NP_primitive = P необходимо, чтобы существовал Mt с полиномиальным временем работы - и к тому же корректный и полный.

Доказательство

Про диагонализацию см. в прошлой постановке задачи - http://dxdy.ru/post956171.html#p956171 , а про построение AntiMt см. начало прошлого доказательства - http://dxdy.ru/post956292.html#p956292 . И там же свойство AntiMt доказано в п. 5 для неравенства (фактического - по работе алгоритмов, а не по теории) вот такое:

Mt(Aks, «AntiMt()») ≠ FormatMt(AntiMt())

В частности, для случая, когда Mt(Aks, «AntiMt()») = knockout получится:

AntiMt() =  Anti(knockout)

Про вывод последнего  равенства - см. пункты 8 (как исходный), 9, 10 того вывода и пункт 1 (это про свойства диагонализации). Условия корректности из прошлого доказательства в нынешнем доказательстве не верны (пункты 6 и 7), поэтому и выводы из них здесь учитывать не следует.

Теперь - как строится Аксиома «диагонального нокаута».

Нам нужно построить утверждение, которое утверждало бы, что

Mt(Aks, «AntiMt(...)») = knockout,

Но надо чтоб в составе Aks было само это выражение. То есть, чтобы Аксиома задавала результат, который должен быть у Mt(Aks, «AntiMt(...)») при данном наборе аксиом.

Многоточие вместо аргумента в AntiMt() означает, что программа AntiMt(), зависящая от аксиом - так же меняет свои аксиомы, как и переменная для аксиом в Mt (где Aks).

То есть, в следующее выражение:

Mt(AddAks(Aks, X), «AntiMt(...)») = knockout

нам надо добавить вместо X такой текст, который выражал бы само это выражение. Это делается при помощи алгоритма diag() вот таким образом:

Mt(AddAks(Aks, diagMt(AddAks(Aks, diag(x)), «AntiMt(...)») = knockout »] ), «AntiMt(...)») = knockout

Назовем приведенное равенство так:  DiagKnockout(Aks). Именно его текст добавляется к аксиомам. Что можно переписать так:

Mt(AddAks(Aks, «DiagKnockout(Aks)»), «AntiMt(...)») = knockout

Получилось эквивалентное равенство, а не то же самое, потому что прошлое равенство и было DiagKnockout(Aks), а данное выражение - это как прошлое, но после того как сработал diag[] с квадратными скобками и вместо него - результат его работы.

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

Если найдется хоть одна непротиворечивая теория, которая будет расширена аксиомой диагонального нокаута и Mt() «согласится» с аксиомой диагонального нокаута, то он сразу будет неполон. Хотя, обосную - почему он будет неполон.

Рассмотрим работу алгоритма Mt(AddAks(Aks, «DiagKnockout(Aks)»), «AntiMt(...)»). Если он выдаст knockout (что и означает «согласится»), то равенство

Mt(AddAks(Aks, «DiagKnockout(Aks)»), «AntiMt(...)») = knockout

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

И в полученной таким образом расширенной теории Mt() неполон из-за своего knockout, потому что в полученной непротиворечивой теории из-за аксиомы диагонального нокаута можно в соответствии с аксиомой Mt(NewAks, «AntiMt()») = knockout в 2 шага (помимо вывода свойств для AntiMt() из леммы о диагонализации) вывести AntiMt() = Anti(knockout) - о чём было сказано в начале нашего доказательства. И после этого в теории есть доказательство для результата работы AntiMt(), которого нет у Mt(). А это и есть неполнота.

Значит, случай, когда Mt() «согласился» хоть в одной теории с аксиомой диагонального нокаута мы рассмотрели и в таком случае Mt() неполон. А в случае если он «не согласился» - теория вообще заведомо противоречива, а его поведение не соответствует аксиомам.

Теорема доказана.

Tags: NP≠P дискуссии, ЖЖвЖЖ математика
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment