Есть много результатов неприемлемости, которые основаны на гипотезе об уникальных играх. Например,
Предполагая гипотезу об уникальных играх, трудно вычислить аппроксимацию задачи максимального разреза в пределах коэффициента R для любой константы R > R GW .
(Здесь R GW = 0,878… - коэффициент аппроксимации алгоритма Геманса – Уильямсона.)
Однако некоторые люди предпочитают использовать термин « UG-hard » как:
Очень трудно аппроксимировать задачу максимального разреза в пределах коэффициента R для любой постоянной R > R GW .
Является ли последний просто сокращением для первых, или они имеют в виду разные заявления?
Ответы:
Более ранняя версия этого ответа была первоначально опубликована NicosM в качестве ответа на вопрос « Последствия уникальных игр, являющихся проблемой NPI ». Поскольку оказалось, что он не отвечает на то, что он хотел спросить, я перенес это на этот вопрос.
Краткий ответ: они означают разные утверждения. Последнее подразумевает первое, но первое не обязательно подразумевает второе.
Длинный ответ: Напомним, что единственной проблемой игры является следующая проблема обещаний.
Уникальная игровая задача с параметрами k ∈ℕ и ε , δ > 0 (1− ε > δ )
Экземпляр : уникальная игра G с одним игроком для двух игроков с размером метки k .
Да-обещание : G имеет значение не менее 1− ε .
Без обещаний : G имеет значение не более δ .
Гипотеза об уникальных играх гласит:
Рассмотрим результаты следующей формы:
(Примером X является проблема аппроксимации максимального среза при некотором постоянном коэффициенте R > R GW .)
Большинство (если не все) результатов вида (1) фактически доказывают следующий факт:
Нетрудно убедиться, что (2) влечет (1). Однако (2) подразумевает больше, чем (1): например, предположим, что однажды мы можем доказать, что вариант гипотезы об уникальных играх, где «NP-complete» заменяется на « GI -hard». Тогда (2) подразумевает что X также GI-жесткий. (1) не подразумевает этого. Вот почему некоторые люди считают, что утверждение (1) не лучший способ сформулировать теорему: (1) слабее, чем то, что фактически доказано, и разница может быть важной.
Хотя (2) является более точным утверждением того, что доказано, оно явно является полным глотком. Вот почему люди придумали сокращение для этого: «Проблема X сложная для UG» - сокращение для (2).
источник