Полиномиальное сокращение времени
В теории сложности вычислений полиномиальное сокращение времени — это метод решения одной задачи с использованием другой. Один показывает, что если существует гипотетическая подпрограмма , решающая вторую задачу, то первую проблему можно решить путем преобразования или сведения ее к входным данным для второй задачи и вызова подпрограммы один или несколько раз. Если и время, необходимое для преобразования первой задачи во вторую, и количество вызовов подпрограммы полиномиальны , то первая задача полиномиально сводится ко второй. [1]
Полиномиальное сокращение времени доказывает, что первая проблема не сложнее второй, потому что всякий раз, когда существует эффективный алгоритм для второй проблемы, он существует и для первой проблемы. Напротив , если для первой задачи не существует эффективного алгоритма, то его не существует и для второй. [1] Полиномиальные сокращения часто используются в теории сложности для определения как классов сложности , так и полных задач для этих классов.
Три наиболее распространенных типа редукции за полиномиальное время, от самых строгих до наименее ограничительных, — это редукция «многие единицы» за полиномиальное время , редукция по таблице истинности и редукция Тьюринга . Наиболее часто используемыми из них являются сокращения «многие единицы», а в некоторых случаях фраза «полиномиальное сокращение времени» может использоваться для обозначения сокращения многих единиц за полиномиальное время. [2] Наиболее общими редукциями являются редукции Тьюринга, а наиболее ограничительными являются редукции типа «многие единицы» с редукциями таблицы истинности, занимающими пространство между ними. [3]
Сведение «много-один» за полиномиальное время от проблемы A к проблеме B (обе из которых обычно должны быть проблемами решения ) - это алгоритм с полиномиальным временем для преобразования входных данных для проблемы A во входные данные для проблемы B , такой, что преобразованный проблема имеет тот же результат, что и исходная проблема. Экземпляр x проблемы A можно решить, применив это преобразование для создания экземпляра y проблемы B , передав y в качестве входных данных для алгоритма задачи B и вернув его результат. Сокращение «многие-единицы» за полиномиальное время также может быть известно как полиномиальные преобразования или сокращения Карпа , названные в честь Ричарда Карпа . Редукция этого типа обозначается или . [4] [1]
Сведение таблицы истинности за полиномиальное время от проблемы A к проблеме B (обе проблемы решения) - это алгоритм с полиномиальным временем для преобразования входных данных для проблемы A в фиксированное количество входных данных для проблемы B , так что выходные данные для исходной проблемы может быть выражено как функция выходов для B . Функция, которая отображает выходные данные для B в выходные данные для A , должна быть одинаковой для всех входных данных, чтобы ее можно было выразить с помощью таблицы истинности . Сокращение этого типа можно обозначить выражением . [5]
