Можно ли показать NP-твердость по Тьюрингу?

19

В статье Рамирес-Альфонсон « Сложность проблемы Фробениуса» доказана, что задача NP-полна с использованием редукций Тьюринга. Это возможно? Как именно? Я думал, что это было возможно только за полиномиальное время много одного сокращения. Есть ли какие-либо ссылки по этому поводу?

Существуют ли два разных понятия NP-твердости, даже NP-полноты? Но тогда я запутался, потому что с практической точки зрения, если я хочу показать, что моя проблема NP-трудна, что мне использовать?

Они начали описание следующим образом:

Сокращение Тьюринга за полиномиальное время от задачи к другой проблеме - это алгоритм A, который решает с помощью гипотетической подпрограммы A 'для решения , что если бы A' был алгоритмом полиномиального времени для то A был бы полиномиальным временем алгоритм для . Мы говорим, что может быть сокращен по Тьюрингу до .п1п2п1п2п2п1п1п2

Задача называется (Тьюринг) NP-трудной, если существует NP-полная задача решения , так что может быть сокращена по Тьюрингу до .п1P 2 P 1п2п2п1

И затем они используют такое сокращение Тьюринга из NP-полной задачи, чтобы показать NP-полноту некоторой другой проблемы.

user2145167
источник

Ответы:

17

Существует (как минимум) два разных понятия NP-твердости. Обычное понятие, которое использует сокращения Карп, утверждает , что язык является NP-трудной , если каждый язык в НП Карп-сводится к . Если мы изменим сокращение Karp на сокращение Cook, мы получим другое представление. Каждый язык, который является Karp-NP-hard, также Cook-NP-hard, но обратное, вероятно, неверно. Предположим , что NP отличается от CONP, и принять ваш любимый NP-полный язык . Тогда дополнением будет Cook-NP-hard, но не Karp-NP-hard.L L LLLLL

Причина , по которой является Кук-NP-трудной , заключается в следующем: принимать какие - либо языка М в НП. Так как L является NP-трудной, существует функция полиномиальных по F , такие , что х М тогда и только тогда F ( х ) L тогда и только тогда F ( х ) ¯ л . Снижение кашевара от М до ¯ L принимает е , вычисляет F ( х ) , проверяет , является ли F ( х ) ¯L¯MLеxMf(x)Lf(x)L¯ML¯Иксе(Икс) и выводит обратное.е(Икс)L¯

Причина , по которой не является NP-трудной (предполагая , что НП отличается от CONP) состоит в следующем. Пусть ¯ L были NP-трудной. Тогда для каждого языка М в CONP, происходит уменьшение полиномиальных по е такое , что х ¯ М тогда и только тогда F ( х ) ¯ L , или, другими словами, х М тогда и только тогда F ( х ) L . Поскольку L находится в NP, это показывает, что M находится в NP, и поэтому coNP L¯L¯MеИксM¯е(Икс)L¯ИксMf(x)LLMNP. Это сразу подразумевает, что NP coNP, и поэтому NP = coNP.

Если некоторые Куки-NP-трудный язык в P, то P = NP: для любого языка М в НП, используйте сокращение Кука L дать алгоритм полиномиального по для М . Таким образом, в этом смысле языки с полным Cook-NP также являются «самыми сложными в NP». С другой стороны, легко видеть , что Кук-NP-трудный = Кук-CONP твердолобые: сокращение Варить L может быть преобразовано к сокращению Кука для ¯ L . Поэтому мы теряем некоторую точность, используя сокращения Кука.LMLMLL¯

Возможно, есть и другие недостатки в использовании сокращений Кука, но я оставлю это другим ответчикам.

Юваль Фильмус
источник
Я еще не полностью понял все это, я должен сказать. Но у меня есть еще один вопрос, может быть, вы можете ответить на него (поскольку других ответов не так много): что если у меня красный цвет Тьюринга. от NP-полной задачи A до некоторой задачи B и красного Карпа. от проблемы B к проблеме C. Устанавливает ли это NP-полноту проблемы C (членство не является проблемой)? И вообще, можно ли назвать проблему B NP-hard или, вернее, (Turing) NP-hard? Благодарность!
user2145167
4
Два сокращения Карпа составляют уменьшение Карпа, а два уменьшения Кука составляют уменьшение Кука. Поскольку уменьшение Карпа также является уменьшением Кука, если вы составляете уменьшение Карпа и уменьшение Кука, вы получаете уменьшение Кука. Но в целом вы не получите сокращение Карпа.
Юваль Фильмус
@YuvalFilmus, не могли бы вы уточнить , что вы хотите иметь в виду , по тогда и только тогда F ( х ) L тогда и только тогда ф ( х ) ¯ L ? xMf(x)Lf(x)L¯
Омар Шехаб
Карп-восстановительный от до L является функция F (полиномиальный по в данном случае) , такой , что х М тогда и только тогда F ( х ) L . Для каждого F , х всегда имеет место , что п ( х ) L тогда и только тогда F ( х ) ¯ L , где ¯ L является дополнением к L (относительно диапазона F ). MLfxMf(x)L f,xf(x)Lf(x)L¯L¯Lf
Юваль Фильмус
6

Все в порядке. Уменьшение Тьюринга за полиномиальное время является уменьшением Кука (как в теореме Кука-Левина), а приведение задачи NP-полного к новой задаче дает NP-твердость (как и уменьшение многочлена за полиномиальное время, сокращение AKA Карпа). Действительно, сокращения Карпа просто ограничены сокращениями Тьюринга в любом случае.

В чем они отличаются (в отношении этого вопроса) - в членстве. Сведение Карпа от проблемы к проблеме в NP показывает, что первое находится в NP. Сокращение Кука в том же направлении не делает.

Люк Мэтисон
источник
Благодарю. Я даже не знал, что кто-то показывает членство, явно используя сокращение Карпа. Но это имеет смысл. Но можно показать членство в NP, используя сокращения Тьюринга в обоих направлениях, верно?
user2145167
1
@ user2145167 нет, ответ Ювала дает полную историю здесь, но вкратце, сокращения Кука слабее, поэтому допускайте больше - например, вы можете перейти от любой проблемы со-НП с помощью преобразования Кука к любой проблеме с полной готовностью, которая не является верно для сокращений Карпа.
Люк Мэтисон