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

22

Есть много результатов неприемлемости, которые основаны на гипотезе об уникальных играх. Например,

Предполагая гипотезу об уникальных играх, трудно вычислить аппроксимацию задачи максимального разреза в пределах коэффициента R для любой константы R > R GW .

(Здесь R GW = 0,878… - коэффициент аппроксимации алгоритма Геманса – Уильямсона.)

Однако некоторые люди предпочитают использовать термин « UG-hard » как:

Очень трудно аппроксимировать задачу максимального разреза в пределах коэффициента R для любой постоянной R > R GW .

Является ли последний просто сокращением для первых, или они имеют в виду разные заявления?

Цуёси Ито
источник
+1 Очень приятно. Спасибо Tsuyoshi за то, что пролил свет на эту важную концепцию в теории сложности.
Мухаммед Аль-Туркистани

Ответы:

15

Более ранняя версия этого ответа была первоначально опубликована NicosM в качестве ответа на вопрос « Последствия уникальных игр, являющихся проблемой NPI ». Поскольку оказалось, что он не отвечает на то, что он хотел спросить, я перенес это на этот вопрос.

Краткий ответ: они означают разные утверждения. Последнее подразумевает первое, но первое не обязательно подразумевает второе.

Длинный ответ: Напомним, что единственной проблемой игры является следующая проблема обещаний.

Уникальная игровая задача с параметрами k ∈ℕ и ε , δ > 0 (1− ε > δ )
Экземпляр : уникальная игра G с одним игроком для двух игроков с размером метки k .
Да-обещание : G имеет значение не менее 1− ε .
Без обещаний : G имеет значение не более δ .

Гипотеза об уникальных играх гласит:

Уникальная игра гипотеза. Для всех констант ε и δ существует постоянная k такая, что единственная игровая задача с параметрами k , ε и δ является NP-полной.

Рассмотрим результаты следующей формы:

(1) Исходя из предположения об уникальных играх, задача X является NP-сложной.

(Примером X является проблема аппроксимации максимального среза при некотором постоянном коэффициенте R > R GW .)

Большинство (если не все) результатов вида (1) фактически доказывают следующий факт:

(2) Там существуют постоянные epsi ; и & delta ; таким образом, что для каждого постоянного к , уникальной игровой задачи с параметрами к , е , и б сводится к X .

Нетрудно убедиться, что (2) влечет (1). Однако (2) подразумевает больше, чем (1): например, предположим, что однажды мы можем доказать, что вариант гипотезы об уникальных играх, где «NP-complete» заменяется на « GI -hard». Тогда (2) подразумевает что X также GI-жесткий. (1) не подразумевает этого. Вот почему некоторые люди считают, что утверждение (1) не лучший способ сформулировать теорему: (1) слабее, чем то, что фактически доказано, и разница может быть важной.

Хотя (2) является более точным утверждением того, что доказано, оно явно является полным глотком. Вот почему люди придумали сокращение для этого: «Проблема X сложная для UG» - сокращение для (2).

Цуёси Ито
источник
8
Это похоже на два утверждения: «(1) Предполагая, что P! = NP, X не имеет алгоритма полиномиального времени» и «(2) X является NP-сложным». (2) подразумевает (1), но (1) не подразумевает (2). На практике мы обычно доказываем (2), хотя мы часто говорим (1), чтобы объяснить значимость доказательства людям, незнакомым с NP-твердостью.
Робин Котари
1
@TsuyoshiIto вы могли бы принять свой собственный ответ :). Это действительно поощряется, и это хорошая справка для будущих гуглеров.
Суреш Венкат
@ Суреш: Спасибо. Вероятно, так и будет, но система требует, чтобы я подождал 48 часов после публикации вопроса, прежде чем принять собственный ответ.
Цуёси Ито
@TsuyoshiIto: Ах, я не осознавал этого. звучит хорошо.
Суреш Венкат
@TsuyoshiIto: хороший четкий ответ! извините, я не выполнил вашу просьбу, чтобы мои комментарии стали ответом на другой вопрос: я был занят, отчасти ленив, отчасти не чувствовал, что пересмотренный вопрос вообще был вопросом.
Сашо Николов