dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

6. Задачи Кука и авторизуемые задачи из класса NP

к Оглавлению

1.1. В силу тезиса Чёрча любой искомый ответ получается от какого-то алгоритма. Значит, среди параметров (аргументов) задачи всегда можно задать тот, который отвечает за алгоритм, дающий ответ. Нужно лишь, чтобы задача была достаточно выразительной и была способна представлять произвольные алгоритмы.

Тогда вместо задачи L(x, y) мы получим задачу L(d, t, y), где аргумент x разделён на 2 аргумента:

t – теорема, для которой надо найти доказательство y;

d – аргумент долга – формальное представление того алгоритма, который ищет доказательство y для теоремы t. Самое простое формальное представление – программный код алгоритма на некотором языке программирования. Если речь о поиске доказательства без учёта ограниченных возможностей каких-либо алгоритмов-решений, то в качестве значения у аргумента долга d будем задавать прочерк «-» и называть такое значение алгоритма долга «объективно».

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

Возьмём хотя бы лемму о диагонализации (лемма и доказательство были приведены выше в подразделе 5.1 «Лемма о диагонализации») – за этой леммой был приведён пример для алгоритма-решения, который «предсказывает» поведение алгоритмов-задач (получая их текст в качестве аргумента). И там был построен «антиалгоритм»: Этот «антиалгоритм» запускает внутри себя алгоритм-решение, передавая ему в качестве аргумента свой собственный программный текст, и поступает иначе, чем «спрогнозирует» алгоритм-решение – если алгоритм-решение остановится. Но, заранее можно сказать, что алгоритм-решение не может предсказать то, какой результат выдаст его «антиалгоритм».

Из этого видно, что в задаче L(d, t, y) может быть задана такая «персональная подсказка» для некого (произвольного) алгоритма-решения M(d, t), что при правильном понимании алгоритмом M(d, t) данной задачи он выдаст ответ 0 («не могу найти доказательство про результат работы AntiMt()») за конечное время. Все нюансы мы подробно рассмотрим в своё время, а сейчас просто намечаем путь исследования.

1.3. Подход с тезисом Чёрча и обязательным наличием какого-то детерминированного алгоритма-решения (верного или не верного), дающего значение для искомого доказательства – верен в детерминированном мире, разумеется, но такова модель наших теорий. И в этом смысле для любой достаточно общей задачи, ответ для которой мы ищем, можно подразумевать не только наличие «исполнителя», дающего (или пытающегося дать) ответ, но и разные (!) правильные ответы для разных исполнителей – вообще говоря.

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

Замечу, что подобная задача «Сфинкс» Sph(d, t, y) с «персональной подсказкой» будет полностью соответствовать реальным фактам – если она корректно сформулирована и заявляет, что алгоритм «Эдип» OedSph(…, …, …)», «-», t) не может найти доказательство y для теоремы t (при аргументе долга «-» - «объективно»), то так оно и будет. И, выдавать своё предсказание, корректно сформулированная задача «Сфинкс» будет полиномиально быстро – относительно размера «Эдипа» и теоремы t – независимо от того, как долго будет работать алгоритм-решение «Эдип». Даже если «Эдип» вообще не остановится.

1.4. Работу алгоритма проверки при аргументе долга «объективно» будем называть «базовым алгоритмом проверки». Но за счет дополнительной информации о некотором (или некоторых) «избранном» алгоритме-решении внутри задачи из NP можно будет заранее знать о его специфических возможностях по решению заданной задачи.

Принцип независимости «базового» алгоритма проверки от алгоритмов-решений назовём «принцип независимости алгоритма проверки». И «персональная информация» не должна вступать в противоречие с «базовой проверкой» - это тоже часть принципа независимости алгоритма проверки. Например:

Если «персональная информация» соответствует невозможности алгоритма-решения «Эдип» найти доказательство при аргументе долга «объективно» для теоремы t, то необходимо, чтобы «Эдип» действительно был не способен сделать это.

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


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.
  • 0 comments