Очень сложная проблема в понятии сокращения

Question

Я много изучал о сокращении, но у меня есть проблема: Я беру это из CLRS:

"..." сводя "решение проблемы A к решению проблемы B, мы используем" легкость "B, чтобы доказать" легкость "A."

И я беру это из "Вычислительной сложности Кристоса Х. Пападимитриу":

«... проблема А, по крайней мере, такая же трудная, как и проблема В, если В сводится к А».

Я запутался с этими двумя понятиями: когда мы используем простоту, мы говорим, что проблема X сводится к проблеме Y, и если у нас есть алгоритм полиномиального времени для Y, а процесс редукции выполняется за полиномиальное время, то проблема X разрешима за полиномиальное время, и X легче, чем Y, или, по крайней мере, не тяжелее, чем Y.

Но когда мы используем твердость, мы говорим, что проблема X сводится к проблеме Y, а Y легче, чем X, или, по крайней мере, не сложнее, чем X.

Я действительно запутался, Пожалуйста, помогите мне. Особая благодарность.

Answer 1

Я думаю, что вы, возможно, пропустили, что первая цитата говорит "уменьшить А до В", а вторая цитата говорит "уменьшить В до А".

Если X сводится к Y, это означает, что Y может бытьЕсли использовать X для решения X, то X не сложнее, чем Y. Это потому, что уменьшение полиномиальной сложности считается «свободным», поэтому, приведя X к Y, мы нашли способ решить X, используя любые решения для Y.

Таким образом, в первой цитате, если A сводится к B, а B легко, это означает, что A легко (строго говоря, это не сложнее).

Во второй цитате используется логический контрапозитив: еслиB сводится к A, а B трудный, тогда A должен быть твердым (строго говоря, это не легче).Доказательство: если A было легко, то B было бы легко (как указано выше, но A и B поменялись местами).B нелегко, поэтому A нелегко.

Ваше утверждение «мы говорим, что проблема X сводится к проблеме Y, а Y легче, чем X, или, по крайней мере, не труднее, чем X», неверно.Возможно, что X уменьшится до Y (то есть мы можем использовать Y для решения X), даже если Y на самом деле на сложнее, чем X. Таким образом, мы можем уменьшить сложение (X) до особого случая.некоторой NP-сложной задачи (Y), определяя схему построения за полиномиальное время экземпляра NP-сложной задачи, решение которой является суммой двух наших входных чисел.Это не значит, что сложность сложна для NP, просто мы сделали вещи излишне трудными для себя.Неразумно использовать это сокращение для выполнения сложения, поскольку есть более эффективные способы сложения.Что ж, лучше предположить, что P! = NP, то есть.

Answer 2

Думайте о сокращении как об уменьшении доказательства проблемы, относящейся к определенному классу, а не уменьшении самой проблемы. Отношение больше связано с логикой, чем со сложностью.

Answer 3

Теория просто так.

У вас есть алгоритм для решения проблемы A, который, как вы знаете, может быть решен за полиномиальное время.

Если возможно преобразовать проблему B в нотациюкоторая может быть решена с помощью задачи A, а затем преобразовать результат обратно в нотацию для задачи B за полиноминальное время, а затем решить проблему B также будет за полиноминальное время - так как общее время - это просто сложение двух полиномов - следовательно, не сложнее.