dmitgu (dmitgu) wrote,
dmitgu
dmitgu

... 7, пп. 6.4-7. NP ≠ P

к Оглавлению

6.4. С учётом пункта 6.2, предыдущего пункта, правила вывода MP мы имеем такие формулы и результат:

Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S)) = 0  AntiOed_S() = 0

Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S)) = 0

AntiOed_S() = 0

Теперь можем дать такой первоначальный ответ на вопрос пункта 6.1 о размере доказательства для теоремы:

AntiOed_S() = 0

Для данной теоремы в случае остановки алгоритма

Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S)) с результатом 0,

доказательство будет иметь размер полиномиальный относительно:

размера |Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S))| , величины n

Где n – количество шагов работы алгоритма «Эдип» – OedSph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s1(S)) – и   в это число n не входит время работы алгоритма s1(S).

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

6.5. Осталось оценить величину n относительно |S| и |s|, чтобы понять, помещается ли доказательство разбираемой теоремы в пределы допустимого размера доказательства S при корректной работе алгоритма «Эдип».

Вспомним последний абзац из пункта 2.4 разделе 6 «Задачи Кука и авторизуемые задачи из класса NP»:

Если для «персональной подсказки» алгоритма «Сфинкс» о возможностях алгоритма «Эдип» имеется ограничивающий полином p_0(|x1|, |x2|, … ) на время получения подсказки, то «Эдип», способный сводить задачи из класса NP к задачам из класса P, найдёт правильный ответ (если он есть) или выдаст 0 (если «персональная подсказка» не содержит правильного ответа) за время, ограниченное некоторым полиномом p(|x1|, |x2|, … ).

Мы рассматриваем именно такие «Эдипы», о которых говорится в процитированном абзаце. Но из пункта 5.5 известно, что время работы «Сфинкса» для интересующих нас случаев ограничено полиномом v*|S|^u, где v, u – фиксированные числа. Значит, корректный «Эдип», который способен сводить задачи из класса NP к задачам из класса P должен выдать свой ответ за время, ограниченное неким полиномом p(|S|). А тогда найдётся и ограничивающий полином для такого времени вида w*|S|^r, где w, r – фиксированные числа.

6.6. Итак, для корректного алгоритма-решения:

Oed(«Sph(…, …, …, …, …)», «-», «AntiOed_S() = 0», S, s), где s =s1(S),

ограничивающий полином для времени n работы такого алгоритма будет равен w*|S|^r, где w, r – фиксированные числа. Разумеется, это один из бесконечного количества ограничивающих полиномов для данного времени работы.

После того, как мы определились с ограничением на величину n, мы можем переписать пункт 6.4 таким образом:

Для теоремы: AntiOed_S() = 0 составленной для корректного алгоритма «Эдип», который способен сводить задачи из класса NP к задачам из класса P доказательство будет иметь размер, не превышающий полином  k*|S|^q, где k, q – фиксированные числа, если фиксированы программы «Сфинкс» и «Эдип».

Каким образом, размер доказательства, ограниченный полиномом k*|S|^q, соотносится с предельным размером доказательства, заданным аргументом S? Соотношение тут – неполиномиальное. При росте S полином k*|S|^q обязательно станет меньше S (сравнивается число и полином от количества десятичных цифр в нём), а это и будет означать неполноту «Эдипа», вернувшего 0 (Ноль) в отношении той теоремы, для которой имеется доказательство в пределах «общего» ограничивающего алгоритма.

Но и не возвращать ответ для «Эдипа» было бы ошибочным, потому что задача построена именно так, чтобы найти доказательство он не мог.

7. Поскольку неполнота «Эдипа» доказана для произвольного алгоритма-решения задачи «Сфинкс», то нет ни одного алгоритма, который мог бы свести построенную нами авторизуемую задачу «Сфинкс» из класса NP к какой-то задаче из класса P. Поэтому неравенство NPP доказано.


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