Алгоритмическая Сводимость

одно из основных понятий алгоритмов теории и ее приложений Возникло в связи с тем, что неразрешимость (и разрешимость) многих алгоритмических проблем устанавливается большей частью не непосредственно, а путем сведения к исследуемой проблеме такой алгоритмич. Проблемы, неразрешимость к-рой уже доказана (или исследуемой проблемы к нек-рой уже решенной проблеме). Так, неразрешимость проблемы гомотопии путей в полиэдре доказывается путем сведения к ней проблемы равенства слов в соответствующей фундаментальной группе. Ниже приведены простейшие примеры А. С. Теоретико-числовых (т. Е. Определенных на натуральных числах) предикатов и функций. где Ри 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. А. А. Мучник.