Почему NP-полные задачи не имеют сходных отношений аппроксимации?

Поскольку 2 NP-полные задачи по определению сводимы друг к другу, поэтому решение одной из них можно получить с помощью черного ящика, решающего другую, почему они не имеют сходных отношений аппроксимации (ссылаясь на их аналоги по оптимизации )? Я предполагаю, что некоторый постоянный или даже полиномиальный дрейф может быть понят, но у нас есть случай алгоритмов аппроксимации с постоянным множителем для некоторых NP-полных задач и, с другой стороны, другие задачи, которые не могут быть даже аппроксимированы алгоритмом аппроксимации полиномиального отношения типа общего TSP? Спасибо

cc.complexity-theory approximation-algorithms reductions N27
источник

потому что сокращения черного ящика только сохраняют аспект ДА / НЕТ проблем (решения), а не близость приближений.

Суреш Венкат

если я уменьшу 3SAT до покрытия вершин, то покрытие вершин размера k подразумевает выполнимость и наоборот. Но если я получу покрытие вершин размером 2k, это не значит, что я смогу удовлетворить половину предложений.

Суреш Венкат

Выберите конкретное сокращение от одной NP-полной задачи к другой и попытайтесь расширить его, чтобы сохранить коэффициенты аппроксимации. Вы увидите, что идет не так.

Питер Шор

Ответ Питера самый лучший на самом деле. Просто попробуйте и посмотрите, что получится. Я думаю, что под философским скептицизмом вы имеете в виду «я не понимаю интуицию». Иногда лучший способ - это просто попробовать несколько примеров и позволить интуиции расти.

Суреш Венкат

\log | C |

$\log |C|$

| C |

$|C|$

| C |^{2}

$|C|^2$

2^{| C |}

$2^{|C|}$

C

$C$

Юкка Суомела

Ответы:

Сокращения определяются в зависимости от версии решения проблемы. Коэффициенты аппроксимации для их версий оптимизации - это отдельный вопрос, который кажется связанным, но не обязательно должен быть. Итак, чтобы ответить на ваш вопрос с философской точки зрения, почему вы должны ожидать, что классовые NPC сохранят отношения аппроксимации, если они не определены в первую очередь по отношению к ним?

Лев Рейзин
источник

«Сокращения определены в отношении варианта решения проблемы». Это правда, скажем, для Левина ?

MS Dousti

Вы правы, не все сокращения определяются версиями решений, но мы можем определить NPC только в терминах сокращений черного ящика, и тогда, я думаю, это может привести к спорам о том, как эти классы меняются с использованным сокращением ... Я должен был сказать «класс NPC определен для решения проблем». Это не совсем точный аргумент, поскольку мы могли бы даже определить класс задач решения, чьи версии оптимизации сохраняют отношения аппроксимации, но это не то, что мы делаем для класса NPC. Я думаю, что вопрос @ N27 является философским возражением, мне позволено дать философский ответ. :)

Лев Рейзин