к Оглавлению
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 для исследования вопроса о поиске доказательств для логических утверждений. Как известно, нет алгоритма, который в общем случае связывал бы размер утверждения и размер его доказательства, а нас интересует возможность найти доказательство – если оно есть – за полиномиальное время относительно каких-то задаваемых нами пределов на размер доказательства. Или же за полиномиальное от заданного размера доказательства время узнать, что нужного доказательства в таких пределах нет.
