Сокращение (сложность)
В теории вычислимости и теории сложности вычислений редукция — это алгоритм преобразования одной задачи в другую. Достаточно эффективное сведение одной задачи к другой можно использовать, чтобы показать, что вторая задача по крайней мере так же сложна, как и первая.
Интуитивно, проблема A сводится к проблеме B , если алгоритм эффективного решения проблемы B (если он существует) также может быть использован в качестве подпрограммы для эффективного решения проблемы A. Если это так, решение A не может быть сложнее, чем решение B. «Сложнее» означает наличие более высокой оценки требуемых вычислительных ресурсов в данном контексте (например, более высокая временная сложность , большие требования к памяти, дорогостоящая потребность в дополнительных аппаратных процессорных ядрах для параллельного решения по сравнению с однопоточным решением и т. д.). . Существование сокращения от A до B может быть записано в сокращенной записи A ≤ m B , обычно с индексом на ≤, чтобы указать тип используемого сокращения (m: сокращение отображения , p: полиномиальное сокращение ).
Математическая структура, созданная на множестве задач редукциями определенного типа, обычно образует предпорядок , классы эквивалентности которого могут использоваться для определения степеней неразрешимости и классов сложности .
Очень простой пример сокращения — от умножения к возведению в квадрат . Предположим, все, что мы умеем, — это складывать, вычитать, возводить в квадраты и делить на два. Мы можем использовать эти знания в сочетании со следующей формулой, чтобы получить произведение любых двух чисел:
У нас также есть сокращение в другую сторону; очевидно, что если мы можем умножить два числа, мы можем возвести число в квадрат. Кажется, это означает, что эти две проблемы одинаково сложны. Этот вид сокращения соответствует сокращению Тьюринга .
Однако сокращение станет намного сложнее, если мы добавим ограничение, согласно которому мы можем использовать функцию возведения в квадрат только один раз и только в конце. В этом случае, даже если нам разрешено использовать все основные арифметические операции, включая умножение, приведения вообще не существует, потому что для того, чтобы получить желаемый результат в виде квадрата, нам нужно сначала вычислить его квадратный корень, а этот квадрат корень может быть иррациональным числом , которое невозможно построить с помощью арифметических операций над рациональными числами. Однако, идя в другом направлении, мы, безусловно, можем возвести число в квадрат с помощью всего лишь одного умножения, только в конце. Используя эту ограниченную форму сокращения, мы показали тот неудивительный результат, что умножение в целом сложнее, чем возведение в квадрат. Это соответствует сокращению «многие к одному» .
