10. Понятие схемы кодирования.

Рассмотрим схему кодирования.

Предположим, например, что условие решаемой задачи представлено графом G=(V,E), где

V – множество вершин,

E – множество рёбер.

Причём, каждое ребро понимается как неупорядоченная пара вершин, которые соединяются.

Условия данной задачи могут быть написаны разными способами.

Способ записи	Цепочка символов	Длина цепочки		V1		V2
Список вершин цепочки	V[1] V[2] V[3] V[4] (V[1] V[2]) (V[2] V[3])	36
Список соседей	(V[2]) (V[1] V[3]) (V[2]) ( )	24
Строки матрицы инциденции	0100 / 1010 / 0100 / 0000	19
				V3		V4

Представленные схемы кодирования дают входы различной длины, однако можно проверить, что они отличаются друг от друга не более чем полиномиальным образом. Это означает, что полиномиальный алгоритм, работающий с входными данными любой из кодировок, в любой другой кодировке будут также иметь полиномиальную сложность. Неформально определяя “разумную” схему кодирования, мы можем выдвинуть два требования к ней:

1. Код любой индивидуальной задачи I должен быть “сжатым”, т.е. не содержать избыточной информации или избыточных символов.

2. Числа, входящие в условие задачи I должны быть представлены в двоичной системе счисления (или с любым другим основанием отличным от 1).

Если ограничимся рассмотрением только тех схем кодирования, которые удовлетворяют этим условиям, то выяснение вопроса о том, является ли данная задача трудно решаемой, не будет зависеть от выбора конкретной схемы кодирования. Все эти схемы будут полиномиально эквивалентны между собой. Аналогичное замечание можно сделать и относительно выбора модели вычислительного устройства. Все известные в настоящей момент времени модели эквивалентны относительно полиномиальновременной сложности. В следующей таблице представлено время, требуемое машиной А для моделирования работы алгоритма сложности T(n) на машине B.

Моделируемая машина B	Моделирующая машина A
	1МТ	kМТ	МПД
М.Т. с 1 лентой	-	O(T(n))	O(T(n)∙logT(n))
М.Т. с k – лентами	O(T2(n))	-	O(T(n)∙logT(n))
Машина произвольного доступа (МПД)	O(T3(n))	O(T2(n))	-

Можно ожидать, что и любая иная “разумная модель” вычислительного устройства будет полиномиально эквивалентна рассмотренной модели. Под словами «разумная модель» мы будем понимать то, что объём работы, выполняемый вычислительным устройством в единицу времени, ограничивается сверху полиномом.

11. Задачи распознавания. Переход от оптимизационной задачи к задаче распознавания

Имеются различия между двумя аспектами труднорешаемости.

Первый аспект состоит в том, что для отыскания решения, требуется экспоненциальное время. Второй аспект заключается в том, что искомое решение настолько велико, что не может быть представлено в виде выражения, длина которого ограничивается полиномом от длины входа. Эта ситуация возникает, например, если в задаче коммивояжера ввести дополнительный параметр B и потребовать найти все маршруты по длине превосходящие B. Мы будем рассматривать только первый аспект решаемости, т.е. будут рассматриваться только те задачи, длина решения которых ограничена полиномом от длины входа.

Первые примеры труднорешаемых задач были построены в 60^х годах, а в 70^х было показано, что большое количество реальных задач относится к труднорешаемым. В число этих задач вошло большое количество задач из теории автоматов, формальной теории языков и математической логики. Однако большинство труднорешаемых практических задач в действительности разрешимы. Более того, они разрешимы за полиномиальное время с помощью недетерминированного вычислительного устройства.