24. Псевдополиномиальные алгоритмы.

Следующие определения предполагают, что с массовой задачей П связаны функции Max и Length, обладающие ранее указанными свойствами. Алгоритм решения задачи П будет называться псевдополиномиальным (по времени) алгоритмом, если его временная функция ограничена сверху полиномом от (Length(I), Max (I)). По определению, любой полиномиальный алгоритм является также и псевдополиномиальным, поскольку ограничен сверху полиномом от первого аргумента (Length(I)). NP-полнота задачи не обязательно исключает возможность её решения псевдополиномиальным алгоритмом. Многие из рассмотренных нами задач обладают тем свойством, что величина Max(I) ограничена полиномом от Length(I), поэтому для таких задач нет различия между полиномиальным и псевдополиномиальным алгоритмами. Например, в задаче клика единственный числовой параметр J ограничен количеством вершин графа. Задача выполнимость не содержит чисел, за исключением индексов, литералов, дизъюнкций, этими числами можно пренебречь, поскольку они играют роль имён. Принятое нами соглашение о разумной схеме кодирования гарантирует, что имена будут ограничены полиномом Length(I).

Выделим класс задач, которые будут рассматриваться в данном разделе. Будем называть задачу П задачей с числовыми параметрами, если не существует такого полинома p, что для любой задачи ID_П Max(I)p(Length(I)). Среди шести основных NP-полных задач единственной задачей с числовыми параметрами является задача разбиение.

Замечание 1.

Если NP-полная задача П не является задачей с числовыми параметрами, то П не может быть решена псевдополиномиальным алгоритмом (если справедливо, что P  NP).

Для произвольной задачи П и полинома p с целыми коэффициентами обозначим через П_p подзадачу, получаемую из П рассмотрением только тех индивидуальных задач I, для которых выполняется Max(I)p(Length(I)). Задача П_p уже не является задачей с числовыми параметрами. Если задача П разрешима псевдополиномиальным алгоритмом, то задача П_p разрешима полиномиальным алгоритмом. Задачу П назовём NP-полной в сильном смысле, если ПNP и существует такой полином p с целыми коэффициентами, что задача П_p является NP-полной.

В частности, если NP-полная задача не является задачей с числовыми параметрами, то она NP-полна в сильном смысле.

Замечание 2.

Если задача П NP-полна в сильном смысле, то она не может быть решена псевдополиномиальным алгоритмом (PNP). Благодаря этому замечанию мы получаем средства для применения теории NP-полноты к вопросам существования псевдополиномиальных алгоритмов.

25. Именная форма. Высказывания. Операции над высказываниями.

Именная форма – это комбинация знаков, которая превращается в имя, если вместо части переменных подставить имена. Данная часть переменных называется свободными переменными, остальные называются связанными переменными. Если в именной форме отсутствуют свободные и связанные переменные, то именная форма сама является именем.

Пример:

Именная форма	Свободные переменные	Связанные переменные	Примечание
0	---	---	Имя
	---	---	=3,14
-		---
X2+Y3	X,Y	---
	---	n
	a,b	x
	a,b,f	x	f-переменная обозначающая функцию.

Определение: Высказывание – это то, о чём осмысленно спросить, истинно оно или ложно.

Пример: То, что я сейчас написал в тетради – ложно. Это не является высказыванием!

Основные операции над высказыванием:

Если обозначить истинность символом 1, а ложность 0, то операции над высказываниями можно задать с помощью таблиц Кэли.

Бинарные операции дизъюнкция и конъюнкция задаются следующими таблицами:

V	0	1
0	0	1
1	1	1

ДИЗЪЮНКЦИЯ

	0	1
0	0	0
1	0	1

КОНЪЮНКЦИЯ

Бинарная операция импликация: АВ

	0	1
0	1	0
1	1	1

Операция эквиваленция:

	0	1
0	1	0
1	0	1

Унарная операция отрицания:

	0	1
	1	0