Изменения

|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 equivalent'', ''m-equivalent'') <tex>B</tex>, если <tex>A\le_{m}B</tex> и <tex>B\le_{m}A</tex>. Обозначение: <tex>A\equiv_{m}B</tex>.