СВОДИМОСТЬ в теории алгоритмов

— понятие, служащее для постановки и решения вопросов «сложности» рекурсивно перечислимых множеств. Принципиальным результатом алгоритмов теории является доказательство существования рекурсивно перечислимых, но не рекурсивных множеств. Поскольку рекурсивно перечислимые (эффективно порождаемые) мн-ва часто встречаются в матем. практике, то, естественно, возник вопрос, все ли рекурсивно перечислимые, но не рекурсивные мн-ва имеют одинаковую алгоритм. «сложность».

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

Кроме понятий -сводимости и -сводимости, имеются еще сводимости — табличная (-сводимость), ограниченная табличная (-сводимость) и др. Все упомянутые сводимости являются транзитивными, т. е. из следует, что (здесь и дальше х принимает значения . Всякое отношение С. позволяет определить отношение эквивалентности: В тогда и только тогда, когда Далее определяется соответствующая степень неразрешимости: мн-ва А наз. семейство Мн-во всех частично упорядочивается следующим соотношением: тогда и только тогда, когда . Если -степень содержит по крайней мере одно рекурсивно перечислимое мн-во, то она наз. рекурсивно перечислимой -степенью. Мн-во всех рекурсивно перечислимых -степеней обозначается через

Осн. исследования степеней касаются изучения строения частично упорядоченных множеств Укажем некоторые важнейшие свойства этих частично упорядоченных множеств. 1) Частично упорядоченные мн-ва являются верхними полурешетками (полуструктурами), т. е. для любых двух элементов из существует их точная верхняя граница Кроме того, является подполурешеткой Это означает, что для их точная верхняя грань в лежит в Полу-решетка не имеет наибольшего элемента, а полурешетка имеет наибольший элемент Полурешетки имеют наименьший элемент Полурешетка континуальна, счетна 5) Полурешетки не являются решетками, т. е. в существуют такие два элемента что для них не существует точной нижней грани.

Перечисленные свойства являются общими для всех С. Однако имеются и различия. Укажем некоторые свойства полурешеток Полурешетка является идеалом полурешетки т. е. из следует, что Полурешетка не является идеалом полурешетки Полурешетка содержит атомы — миним. элементы: такие элементы что От и из следует, что или Полурешетка удовлетворяет следующему свойству плотности: если то существует такой, что . В частности, не содержит атомов.

В исследованиях по С. часто рассматривают еще одну операцию на — операцию «скачок». Не давая точного определения, можно сказать, что скачком Г-степени мн-ва А является Г-степень наибольшего относительно Г-сводимости мн-ва, которое «рекурсивно перечислимо» в А. Операция «скачок» используется и при построении иерархий в теории рекурсивных ф-ций.

Все упомянутые понятия С. ввел Э. Пост. Следует сказать, что это понятие в теории алгоритмов применяют не только для С. множеств, как было рассмотрено выше. Можно указать еще на С. нумераций (см. Нумераций теория). С. множеств можно рассматривать как С. соответствующих проблем разрешения (проблема разрешения для мн-ва А состоит в вычислении характеристической ф-ции ). Однако в теории алгоритмов возникают и др. проблемы, напр., проблема отделимости (отделения) для множеств А и В, состоящая в вычислении хотя бы одной ф-ции, равной 1 на А и 0 на В. Указанные две проблемы являются частными примерами общего понятия массовой проблемы. Существует понятие С. для массовых проблем, использующее понятие частично рекурсивного оператора. Соответствующие степени трудности массовых проблем образуют частично упорядоченное мн-во М, которое оказывается решеткой. Полурешетка имеет естественное вложение в решетку М.

Лит.: . Ю. Л. Ершов.