dmitgu (dmitgu) wrote,
dmitgu
dmitgu

... 1, пп. 2-3. Задачи … NP и P, NP+ и P+.

к Оглавлению

2.1. Данная задача будет из класса P, если есть алгоритм M(x), который в пределах полиномиального от |x| времени (количество шагов работы алгоритма M(x) – в пределах p(|x|)) возвращает:

y, если имеется y, такой что L(x, y) = 1,

0, если такого y нет.

2.2. Алгоритмы вроде p_0(|x|) , которые ограничивают допустимый размер доказательств, допустимое время работы и т.п. будем называть ограничивающими алгоритмами.

2.3. В дальнейшем мы дополним аргумент «теорема» несколькими аргументами с ограничивающими параметрами. А ограничивающий алгоритм окажется зависимым не только от размера «теоремы с параметрами» – вроде p_0(|d|, |t|, |S|), но и от самих аргументов - вроде pd, t_0(|S|). То есть, при фиксировании части аргументов мы получаем некую новую (под)задачу со специфическим ограничивающим алгоритмом. При этом остаётся в силе и «общий» ограничивающий алгоритм p_0(|d|, |t|, |S|). Мы ещё вернёмся к этому нюансу в пункте 2.4 раздела 6 «Задачи Кука и авторизуемые задачи из класса NP».

3.1. Но надо учитывать и условность полиномиального соотношения между размерами |x| и |y|. Дело в том, что нет алгоритма в общем случае, который устанавливал бы соотношение между размером теоремы и размером её доказательства – когда доказательство есть. В противном случае у нас был бы негативный тест на доказуемость, что, как известно из логики, не имеет места.

Да и в самой теории алгоритмов данное соотношение  p_2(|x|) (в цитате ниже названное q(|x|)) между размером теоремы («слова») и доказательством («свидетелем») потребовалось лишь для ограничения количества рассматриваемых «свидетелей» для заданного «слова»:

«Полиномиальное ограничение q(|x|) на длину свидетелей ограничивает перебор потенциальных свидетелей» - Раздел 16.4 «Класс NP» в учебном пособии для бакалавров по направлению «Информатика и вычислительная техника» и «Информационные системы» В.Н. Крупский, В.Е. Плеско «Математическая логика и теория алгоритмов». То есть, полиномиальность соотношения q(|x|) – весьма условна.

С учётом этого будем подразумевать и такой вариант пункта 1.4:

3.2 или 1.4+. Из аргумента x за полиномиальное количество шагов от размера |x| можно выделить (определение!) «параметр предельного размера доказательства» S – который задаёт максимальный размер для |y|, при превышении которого L(x, y) вернет 0. Записывать в таком случае L(x, y) можно и в виде L(t, S, y) – сразу разбивая x на содержательную часть t и параметр предельного размера доказательства S. Считаем |y| ≤ S(x), где S(x) работает полиномиальное время от размеров |x|, либо S имеется в готовом виде – когда алгоритм проверки имеет вид L(t, S, y).

При этом число S представлено в позиционном виде – как десятичное число, например. Разумеется, если x содержит внутри себя ещё и S, то x будет уже не просто «теорема», а «теорема + наибольшая длина доказательства». И выделить число S из аргумента x тогда можно быстро и просто.

Композиция q_0(x) = p_1(|x|, S(x)) задаёт ограничение на время работы L(x, y) относительно x, и это время конечно и полиномиально относительно размера |x| и размера |y|.

А ограничение на размер |y| вычисляется из аргумента x алгоритмом S(x), который полиномиальный по времени своей работы относительно размеров |x|.

А если алгоритм проверки имеет вид L(t, S, y), то q_0(x) = p_1(|t|, S). Последний вариант более естественный для поиска доказательств, предельный размер которых задан аргументом S – который может быть самым произвольным и записанным в десятичном, например, виде.

3.3. Если вместо пункта 1.4 используется пункт 3.2 (1.4+), то для таких задач определим класс NP+. Очевидно, что пункт 1.4+ превращается в п. 1.4 в случае, когда S(x) = p_2(|x|).

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


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