dmitgu (dmitgu) wrote,
dmitgu
dmitgu

Category:

3. Сложность вопроса о NP ≠ P

к Оглавлению

Разберем следующую задачу, которую можно взять за основу для построения задачи из класса NP:

1. У нас есть теория Th первого порядка (один из вариантов – теория Пеано, например) со списком аксиом

2. У нас есть некоторое утверждение x, истинность которого в рамках данной теории надо проверить

3. У нас есть текст доказательства y

Наша задача – проверить при помощи алгоритма L(x, y) является ли доказательство y доказательством для утверждения x в рамках теории Th. То есть, алгоритм L(x, y) у нас разный для разных Th, ну или он просто зависит от ещё одного аргумента – списка аксиом Th. Однако про зависимость L(x, y) от Th будем помнить, но не будем пока загромождать обозначение лишними для наших рассуждений значками.

Благодаря Гильберту и его современникам мы знаем, что такие алгоритмы можно построить и они довольно простые. На базе данного алгоритма можно построить и задачу из класса NP – проверяя предварительно размер |y| на соответствие некоторым полиномиальным ограничениям p_2(|x|), но это ничего не меняет в следующих рассуждениях, потому что в логике всегда можно найти утверждение любого размера, эквивалентное заданному. Ведь эквивалентное теореме утверждение любого размера всегда можно построить тривиальным добавлением конъюнктивных членов (1=1), например.

Разбираясь с задачей из NP на базе проверки доказательств, мы столкнемся с вопросом о непротиворечивости. И не решив вопрос непротиворечивости – не сможем доказать, что наша задача из NP не сводится к задаче из класса P. А дело вот в чём:

Если теория противоречива, то начиная с доказательства о противоречии, мы моментально доказываем всё что угодно из тавтологии:

~A A X, где X произвольно, а переписать данную тавтологию можно в виде: A (~A X)

Тогда, если у нас есть противоречие – доказаны ~A и A, то при помощи правила вывода MP мы можем отбросить первую посылку из A (~A X) т.к. «истинно» A, а затем и вторую из ~A X, т.к. истинно ~A. И докажем любой X.

Получается, что для противоречивой теории вопрос о поиске доказательства решается за полиномиальное время от размера теоремы: достаточно найти доказательство противоречия (хоть перебором), а затем время составления всех остальных доказательств будет зависеть от размера доказываемого (любого!) утверждения X – линейно.

А это значит, что уровень сложности вопроса о невозможности свести разбираемую задачу на основе теории Пеано из класса NP к задаче из класса P не уступает уровню сложности доказательства непротиворечивости теории Пеано. Доказательство непротиворечивости теории Пеано имеется – и не одно, но их сложность превосходит теоремы Гёделя о неполноте, например. Ну, или доказательство, что данная задача на базе теории Пеано из NP не сводиться к задаче из P должно явно опираться на факт непротиворечивости теории Пеано, например. Тогда сложная часть доказательства – обоснование непротиворечивости – будет «импортирована» из другого доказательства как готовое знание.

Поэтому разбираемая нами задача на базе теории Пеано (или её расширения) может оказаться сложнее, чем вопрос о неравенстве NPP: Возможно, найдётся такая задача в классе NP, про которую удастся доказать, что её нельзя свести к задаче из класса P, но при этом сложность задачи будет не настолько большой, чтобы вставал вопрос о доказательстве непротиворечивости.

Однако, по теореме Кука любая задача из класса NP может быть сведена к КНФ (конъюнктивной нормальной форме) из логики высказываний. А в логике высказываний нет никаких проблем с непротиворечивостью. Поэтому возникает сомнение в правильности теоремы Кука – в отношении хотя бы задач из NP на базе теории Пеано. И это сомнение – как будет показано в разделе 6 «Задачи Кука и авторизуемые задачи из класса NP» – оправдано.

Пока же отметим, что если теорема Кука ошибочна, то при её использовании могут неявно возникать противоречия, а это может приводить к противоречиво построенной задаче, а противоречивая задача, в случае, если она строится на базе проверки доказательств, оказывается из класса P. Но это будет – если речь о «NP-полной» задаче из теоремы Кука – информация о классе NP в целом. И в силу этого использование теоремы Кука потенциально может создавать «доказательства» для равенства 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