6.1. т-сводимость

Мы уже встречались с таким приёмом: чтобы дока­зать неразрешимость некоторого множества X (напри­мер, множества всех номеров всех где-то определённых функции), мы показывали, что если бы оно было раз­решимо, то и любое перечислимое множество К было разрешимо. Для этого мы строили вычислимую функ­цию / так, чтобы принадлежность любого числа п мно­жеству К определялась принадлежностью числа f(n) множеству X.

Сейчас мы изучим такие ситуации более подробно.

Говорят, что множество А натуральных чисел т-сво-дится к другому множеству В натуральных чисел, ес­ли существует всюду определённая вычислимая функ­ция /: N —У N с таким свойством:

f(x) Є В

для всех ж Є N. Такая функция называется т-сводящей А к В. Обозначение: А <^т В.

Теорема 31. (а) Если А <^т В ж В разрешимо, то А раз­решимо, (б) Если А <^т В ж В перечислимо, то А перечи­слимо, (в) А <^т А; если А <^т В ж В <Ст С, то А <^т С. (г) Если А ^т В, то N \ А ^т 1Ц\В.

<] Все эти свойства почти очевидны. Пусть А <^т <Ст В ж мы имеем разрешающий алгоритм для В. Чтобы узнать, принадлежит ли данное х множеству А, мы вычи­сляем f(x) ж узнаём, принадлежит ли f(x) множеству В. Другими словами, а(х) = b(f(x)), если а — характеристи­ческая функция множества А, а Ь — характеристическая функция множества В; поэтому если Ь вычислима, то и а вычислима как композиция вычислимых функций.

Такое же равенство можно записать для «полухарак­теристических» функций, поэтому из перечислимости Вследует перечислимость А. Можно сказать и иначе: мно­жество А является прообразом перечислимого множе­ства В при вычислимом отображении /, и потому пере­числимо.

Тождественная функция, очевидно, m-сводит А к А. Если функция / сводит А к В, а функция g сводит В к С, то

хеАе> f(x) £5о g(f(x)) е С, так что композиция функций g и / сводит А к С.

Наконец, функция, сводящая А к В, будет сводить и N \ А к N \ В. >

Буква «гго> в названии исторически происходит из термина «many-one-reducibilityi>; впрочем, как отмеча­ет М.Сипсер в своём учебнике по теории сложности вычислений, вместо этого лучше говорить «mapping ге-ducibilityi) (сводимость с помощью отображений), сохра­няя букву т в обозначении.

Отметим, что это определение не симметрично отно­сительно перехода к дополнению, если это делается толь­ко в одном из множеств: вовсе не обязательно А <^т Ж\ А, хотя всегда А <^т А.

43. Покажите, что А Щ \ А для перечислимого нераз­решимого множества А.

Отметим, что множества 0 и N являются особыми случаями для m-сводимости. Например, любое разреши­мое множество А сводится к любому множеству В, если только В не является пустым и не совпадает с N. В са­мом деле, если p(EB,q(/zBmA разрешимо, то сводящую функцию можно построить так:

f(x) = if х £ A then р else q fi.

Если же В пусто или совпадает с N, то только пустое множество (соответственно N) сводится к В.

44. Существует ли множество натуральных чисел, к кото­рому m-сводится любое множество натуральных чисел?