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

Термин `Алгоритмическая Сводимость` по словарям
АЛГОРИТМИЧЕСКАЯ СВОДИМОСТЬ

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

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