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))	-

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