M-сводимость — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition=Множество <tex>A</tex> '''m-сводится''' (''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\le_{m}B</tex>.
+
|definition=Множество <tex>A</tex> '''m-сводится''' (является ''many-one reducible'', ''m-reducible'') ко множеству <tex>B</tex>, если существует всюду определённая вычислимая функция <tex>f : x\in A\Leftrightarrow f(x)\in B</tex>, то есть <tex>f(A) \subset B</tex> и <tex>f(\overline{A}) \subset \overline{B}</tex>. Обозначение: <tex>A\le_{m}B</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 27: Строка 27:
 
Например:
 
Например:
 
* [[Примеры неразрешимых задач: проблема соответствий Поста|неразрешимость проблемы соответствий Поста]].
 
* [[Примеры неразрешимых задач: проблема соответствий Поста|неразрешимость проблемы соответствий Поста]].
 +
 +
==Сведение по Тьюрингу==
 +
{{Определение
 +
|definition=
 +
Язык <tex>L</tex> '''сводится по Тьюрингу''' (является ''Turing reducible'') к языку <tex>M</tex>, если язык <tex>M</tex> является разрешимым с использованием <tex>L</tex> как оракула, обозначается как <tex>L \le_T M</tex>.
 +
}}
 +
 +
{{Определение
 +
|definition=Язык <tex>L</tex> '''эквивалентен по Тьюрингу''' (''Turing equivalent'') языку <tex>M</tex>, если <tex>L \le_T M</tex> и <tex>M \le_T L</tex>, обозначается как <tex>L \equiv_T M</tex>.
 +
}}
 +
 +
=== Свойства ===
 +
* рефлексивность: <tex> L \le_T L </tex>
 +
* транзитивность: из <tex> L \le_T M </tex> и <tex> M \le_T N</tex> следует <tex> L \le_T N </tex>
  
 
== Литература ==
 
== Литература ==

Версия 19:20, 18 января 2014

Определение:
Множество [math]A[/math] m-сводится (является many-one reducible, m-reducible) ко множеству [math]B[/math], если существует всюду определённая вычислимая функция [math]f : x\in A\Leftrightarrow f(x)\in B[/math], то есть [math]f(A) \subset B[/math] и [math]f(\overline{A}) \subset \overline{B}[/math]. Обозначение: [math]A\le_{m}B[/math].


Определение:
[math]A[/math] m-эквивалентно (many-one equivalent, m-equivalent) [math]B[/math], если [math]A\le_{m}B[/math] и [math]B\le_{m}A[/math]. Обозначение: [math]A\equiv_{m}B[/math].

Свойства

  1. [math]A\le_{m}A[/math].
    • Доказательство: [math]f(x)=x[/math].
  2. Если [math]A\le_{m}B[/math] и [math]B[/math] разрешимо, то [math]A[/math] разрешимо.
    • Доказательство: Пусть [math]p[/math] — программа-разрешитель для [math]B[/math]. Тогда для любого [math]x\in A[/math] разрешитель должен вернуть значение [math]p(f(x))[/math].
  3. Если [math]A\le_{m}B[/math] и [math]B[/math] перечислимо, то [math]A[/math] перечислимо.
    • Доказательство: Аналогично предыдущему свойству.
  4. Если [math]A\le_{m}B[/math] и [math]B\le_{m}C[/math], то [math]A\le_{m}C[/math].
    • Доказательство: Если [math]f:A\to B[/math] и [math]g:B\to C[/math], то m-сводящая функция [math]h:A\to C[/math] выглядит так [math]h(x) = g(f(x))[/math].

Применение

Лемма:
Если [math]A\le_{m}B[/math] и [math]A[/math] неразрешимо, то [math]B[/math] неразрешимо.
Доказательство:
[math]\triangleright[/math]
Следует из второго свойства.
[math]\triangleleft[/math]

Приведённая лемма позволяет доказывать алгоритмическую неразрешимость некоторой задачи, сводя к ней (а не наоборот!) другую, неразрешимость которой уже доказана.

Например:

Сведение по Тьюрингу

Определение:
Язык [math]L[/math] сводится по Тьюрингу (является Turing reducible) к языку [math]M[/math], если язык [math]M[/math] является разрешимым с использованием [math]L[/math] как оракула, обозначается как [math]L \le_T M[/math].


Определение:
Язык [math]L[/math] эквивалентен по Тьюрингу (Turing equivalent) языку [math]M[/math], если [math]L \le_T M[/math] и [math]M \le_T L[/math], обозначается как [math]L \equiv_T M[/math].


Свойства

  • рефлексивность: [math] L \le_T L [/math]
  • транзитивность: из [math] L \le_T M [/math] и [math] M \le_T N[/math] следует [math] L \le_T N [/math]

Литература