Математическая энциклопедия - алгоритмическая сводимость

одно из основных понятий алгоритмов теории и ее приложений Возникло в связи с тем, что неразрешимость (и разрешимость) многих алгоритмических проблем устанавливается большей частью не непосредственно, а путем сведения к исследуемой проблеме такой алгоритмич. проблемы, неразрешимость к-рой уже доказана (или исследуемой проблемы к нек-рой уже решенной проблеме). Так, неразрешимость проблемы гомотопии путей в полиэдре доказывается путем сведения к ней проблемы равенства слов в соответствующей фундаментальной группе.

Ниже приведены простейшие примеры А. с. теоретико-числовых (т. е. определенных на натуральных числах) предикатов и функций:

где Ри Q - предикаты. Проблема разрешения предиката Р, т. е. установления истинности и ложности Рдля разных х, сводится к проблеме разрешения Q, или, короче, Рсводится к Q. Говорят также, что множество истинности Р, т. е. , сводится к

Пусть

где и теоретико-числовые функции. Проблема вычисления функции f сводится к проблеме вычисления g, или, короче, f сводится к g.

Понятие А. с. было уточнено А. М. Тьюрингом (А. М. Turing): если, грубо говоря, нек-рая Тьюринга машина перерабатывает последовательность закодированных значений функции в последовательность закодированных значений функции f, то функция f сводится к функции g. Близкое понятие относительной вычислимости С. К. Клини (S. С. Kleene) уточнил с помощью рекурсивных схем равенств (см. [1]). После арифмети-зации каждая алгорптмич. проблема сводится к проблеме вычисления нек-рой теоретико-числовой функции f. Если f сводится к gпо Тьюрингу, , a gсводится к f, , то говорят, что f и gимеют одну и ту же степень неразрешимости, или Отношение рефлексивно и транзитивно. Таким образом, все функции (и множества натуральных чисел или их характеристич. предикаты) разбиваются на классы эквивалентности, наз. тьюринговыми степенями или Т-cтепенями (см. [3]). Большинство алгоритмич. проблем, рассматриваемых в логике и математике, являются проблемами разрешения (рекурсивно) перечислимых множеств конструктивных объектов. В связи с этим Э. Л. Пост [2] в 40-х гг. 20 в. предпринял исследование перечислимых множеств и ввел наряду с тьюрпнговой нек-рые специальные виды А. с., сформулировав проблему (сводимости): сводятся ли (по Тьюрингу) друг к другу различные перечислимые неразрешимые множества? Позже было установлено, что перечислимые множества образуют бесконечную весьма богатую систему Т-степеней. При этом был найден так наз. метод приоритета, широко используемый в теории алгоритмов.

В дальнейшем степени неразрешимости нашли применение в других областях математики. Так, напр., для всяких T-степеней аи bперечислимых множеств при существует конечно определенная группа, в к-рой проблема равенства слов имеет степень а, а проблема сопряженности степень b. Имеется тесная связь между степенями (относительно различных видов А. с.) перечислпмых множеств и скоростью роста сложности начальных фрагментов перечислимых множеств. Специальный вид сводимости полиномиальная сводимость, или р- сводимость (сводимость с нек-рым ограничением на время),используется при доказательстве универсальности алгоритмич. проблем "переборного типа", т. е. проблем комбинаторного характера из разных областей математики (см. [5]; более подробную лит. см. в [1]). В свою очередь, при исследовании степеней стали применять методы теории меры (см. [1], гл. 16) и вынуждения метод (см. [4]).

Лит.:[1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972, гл. 9, 10, 13, 16; [2] Роst Е. L., "Bull. Amer. Math. Вез.", 1944, v. 50, № 5, p. 284-316; [3] Кleene S.C., PostE.L., "Ann. Math.", ser. 2, 1954, v. 59, №3, p. 379-407; [4] Selman A. L., "Proc. bond. Math. Soc.", ser. 3, 1972, v. 25, № 4, p. 586-602; [5] Карп Р., в кн.: Кибернетический сборник, в. 12, М., 1975. А. А. Мучник.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985