dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

... 6, пп. 4-5. Задачи … из класса NP

к Оглавлению

4.1. Заметим, что «персональная подсказка» для «Эдипа» про его возможность доказать теорему t – это вовсе не ответ 0 на все доказательства, которые не может дать «Эдип». «Эдип» даёт в лучшем случае одно доказательство для заданной ему для доказывания теоремы, а может и вовсе не остановиться, и не дать ничего. «Персональные подсказки» - это обычный (при аргументе долга «объективно») результат алгоритма проверки, в котором исключены из числа корректных те доказательства, которые алгоритм-решение не может выдать по какой-то причине. Например:

Все доказательства, доказывающие данную теорему про «АнтиЭдип», кроме тех доказательств, которые «Эдип» не может доказать в силу того, что он не может предсказать поведение «Анти-Эдипа».

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

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

Также и «персональная подсказка» для «Эдипа» - оставляет без «запрета» какие-то варианты ответов, которые для «Эдипа» исключены. Зато «персональная подсказка» может быть получена полиномиально быстро.

И для всех «обычных» (не «Эдипов» в отношении теоремы t) алгоритмов-решений тогда будет верно равенство:

Sph(«NotOed(«Sph(…, …, …)», «-», …)», t, y) = Sph(«-», t, y)

4.2. Таким образом, задача из класса NP в общем случае подразумевает наличие у алгоритма- проверки ответов, зависящих от алгоритмов-решений (ответы, зависящие от аргумента долга с соответствующим значением). Выделение аргумента долга в отдельный аргумент – операция условная. Со времён «канторовой пары», известно, что в одно значение (в один аргумент) можно полиномиально быстро «упаковать» и «распаковать» сколько угодно много значений. Но может оказаться и так, что в задаче из NP не существует никаких «персональных подсказок». Тогда мы получаем «классическую» задачу из NP или «задачу Кука». Дадим определение:

Классические задачи из NP (или задачи Кука) - те, которые нельзя свести к задачам со значимым аргументом долга. Классическая задача – это задача из NP с незначимым аргументом долга (когда для всех алгоритмов-решений информация одинаковая).

Чтобы как-то отличить «не классические» задачи из NP от задач Кука, назовём неклассические задачи – «авторизуемые задачи из класса NP». «Авторизация» - термин из сферы IT. Такое название отражает то обстоятельство, что для решения данных задач от алгоритма-решения требуется способность отличать «себя» от «не себя», требуется уметь использовать соответствующую «тебе» персональную информацию, которую может выдать при соответствующем запросе алгоритм проверки.

4.3. И задачу Кука действительно можно свести к КНФ (конъюнктивной нормальной форме), как это делается в теореме Кука. Отмечу только, что посылка теоремы Кука о наличии готовой информации об ограничивающем алгоритме (для времени работы алгоритма проверки) ошибочна. Но можно, видимо, исправить данную ошибку перебором «кандидатов» в ограничивающие алгоритмы в виде 2^n*x^{2^n }. Тогда для какого-то n будет достигнут (если это действительно задача Кука) ограничивающий алгоритм (с «перелётом» степени, скорее всего, но всё равно полиномиальный), а предыдущих i < n шагов будет лишь логарифмическое количество от найденного n, что не повлияет на полиномиальность.

Разумеется, предлагаемое исправление ошибки в теореме Кука не позволяет, вообще говоря, отличить задачи из NP от тех, для которых ограничивающего алгоритма нет. Это и закономерно –нет отрицательного теста на остановку алгоритма и, следовательно, нет отрицательного теста на принадлежность алгоритма к классу NP (с наличием ограничивающего алгоритма). Что очевидно с учётом пункта 5 из раздела 1 «Задачи из классов NP и P, NP+ и P+».

Если же задача является задачей Кука, то предложенный перебор n будет конечным, так как решение в каждом испытываемом случае допускает проверку при помощи алгоритма проверки – одинаковом для всех алгоритмов-решений. Однако для авторизуемых задач из NP дело обстоит иначе (и не только в отношении проверки).

4.4. Ясно, что превращение в КНФ – это разбор программного текста алгоритма проверки и приведение его к специальному виду – с целью некого стандартного анализа, если таковой имеется.

И разбор программного кода в общем случае необходим, потому что просто запускать алгоритм проверки при разных аргументах и таким путём найти нужное доказательство – не получится быстро: это неполиномиально долгий перебор. Поэтому выход – в анализе текста программы, а уж как делать этот анализ – через приведение к КНФ или иначе – вопрос второй.

4.5. Интересно, что в основе задачи Кука может быть и теория Пеано, которая, вроде бы, не сводится к логике высказываний. Но сама по себе проверка доказательств – действие исключительно простое – поэтому на него и опирается весь формализм – и в логике высказываний, и в сложных теориях первого порядка. Подобную проверку можно сводить к логике высказываний. Но! – когда речь идёт о свойствах алгоритмов и их возможностях по выдаче результатов – то тогда иное дело.

И алгоритм проверки «Сфинкс» с «персональной подсказкой» содержит в себе не просто обычный алгоритм проверки доказательств, но и выражает зависимость результата проверки от некого алгоритма («Эдипа»). А это уже задействует более богатые возможности теории Пеано, чем те, которые мы используем при проверке доказательств. И вот здесь к логике высказываний задача уже – не сводится.

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

Интересные подробности о необходимости выхода за рамки логики высказываний для математики можно почитать в «Основаниях математики»: 

Без индивидных переменных и индивидных символов логика высказываний «… обходит стороной один очень существенный логический момент, а именно – отношение сказуемого к подлежащему, т.е. связь между субъектом и предикатом» - «Основания математики» Д. Гильберт, П. Бернайс, Том 1, Глава IV «Формализация процесса вывода II: Исчисление предикатов», Параграф 1. «Введение индивидных переменных …». И далее – использование функций с индивидными символами и переменными, любое корректное сочетания которых представляет из себя «терм» - «Основания математики» Д. Гильберт, П. Бернайс, Том 1, Глава V «Исчисление предикатов с равенством …», Параграф 1. «Расширенный формализм», п. 5 «Добавление функциональных знаков: понятие терма …».

5.1. Здесь перед алгоритмом-решением возникает дополнительная сложность – понять, что речь «о тебе». Но это одна из решаемых сложностей и чем она принципиально отличается от любых других сложностей при поиске ответа на вопрос? Сложности бывают самые невероятные и у многих сложностей – нет пока что способа решения (а у некоторых неразрешимых вопросов вообще никогда не будет решения в общем случае) – в отличие от «распознания себя». Для такого распознания подходит, например, метод диагонализации.

Есть полиномиально быстрая информация о возможностях данного алгоритма? Да. Является ли эта задача из класса NP? Да. Можно поставить вопрос о возможности данного алгоритма-решения выдать соответствующий ответ за время, полиномиальное от времени на получение данной «персональной подсказки»? Да. Будет ли этот ответ из класса P для такой подзадачи? Да.

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

5.2. И, разумеется, у нас нет интереса к «неклассическим» задачам из P – мы доказываем неполноту именно относительно сведения NP к «обычным» задачам из P (или NP+ к P+) и другими здесь не интересуемся.


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