Многократное сокращение

В теории вычислимости и теории вычислительной сложности редукция « многие-один » (также называемая редукцией отображения ^[1] ) — это редукция , которая преобразует экземпляры одной проблемы решения в экземпляры второй проблемы решения, где экземпляр, сведенный к, находится в языке , если исходный экземпляр был на своем языке и не находится на этом языке , если исходный экземпляр был не на его языке . Таким образом, если мы можем решить, находятся ли экземпляры в языке , мы можем решить, находятся ли экземпляры в его языке, применяя редукцию и решая ${\ Displaystyle L_ {1}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L_ {1}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L_ {1}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L_ {1}}$ ${\ Displaystyle L_ {2}}$ . Таким образом, сокращения могут использоваться для измерения относительной вычислительной сложности двух задач. Говорят, что это сводится к тому , если с точки зрения непрофессионала решить труднее, чем . Другими словами, любой алгоритм, который решает, может также использоваться как часть (в остальном относительно простой) программы, которая решает . ${\ Displaystyle L_ {1}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L_ {1}}$ ${\ Displaystyle L_ {2}}$ ${\ Displaystyle L_ {1}}$

Редукции «многие единицы» — это частный случай и более сильная форма редукций Тьюринга . ^[1] При редукции «многие единицы» оракул (то есть наше решение для B) может быть вызван только один раз в конце, и ответ нельзя изменить. Это означает, что если мы хотим показать, что проблема A может быть сведена к проблеме B, мы можем использовать наше решение для B только один раз в нашем решении для A, в отличие от редукции Тьюринга, где мы можем использовать наше решение для B столько раз, сколько необходимо при решении А.

Это означает, что редукция «многие единицы» отображает экземпляры одной проблемы в экземпляры другой, в то время как редукция Тьюринга вычисляет решение одной проблемы, предполагая, что другую проблему легко решить. Редукция «многие-один» более эффективна при разделении задач на отдельные классы сложности. Однако повышенные ограничения на многократные сокращения затрудняют их поиск.

Редукция «многие единицы» была впервые использована Эмилем Постом в статье, опубликованной в 1944 году. ^[2] Позже Норман Шапиро использовал ту же концепцию в 1956 году под названием « сильная сводимость» . ^[3]