На этом шаге мы рассмотрим понятие полиномиальной сводимости.
Будем говорить, что задача Q сводится к задаче P за полиномиальное время, если существует детерминированный полиномиальный алгоритм, преобразующий произвольный частный случай задачи Q (частную задачу, полученную подстановкой значений вместо параметров общей задачи Q) в некоторый частный случай задачи P, и второй детерминированный полиномиальный алгоритм, преобразующий решение задачи P в решение задачи Q.
Это понятие может быть проиллюстрировано рисунком 1.
Рис.1. Сведение задачи Q к задаче P
Для задач распознавания понятие полиномиальной сводимости формулируется чуть проще: задача Q сводится к задаче P за полиномиальное время, если существует детерминированный полиномиальный алгоритм, преобразующий произвольный частный случай задачи Q в некоторый частный случай задачи P так, что ответом для данного случая задачи Q является "да" тогда и только тогда, когда ответом на соответствующий случай задачи P также является "да".
Рассмотрим пример полиномиального сведения. Пусть требуется решить систему линейных уравнений Ax = b с квадратной матрицей А размером n*n, имеющей отличный от нуля определитель det А <> 0. Это задача Q с исходными данными A и b. Вторая задача (Р) формулируется следующим образом: дана квадратная матрица A; требуется найти обратную матрицу C = A-1.
Пример полиномиального сведения можно увидеть на рисунке 2.
Рис.2. Пример полиномиального сведения
Здесь вектор b, несущественный для задачи P, напрямую передается во второе (заключительное) полиномиальное преобразование.
На следующем шаге мы рассмотрим класс сложности задач NP.
