Литература по вопросу из теории вычислительной сложности

[technocrator]

Напомните примеры литературы, где подробно разбирается вопрос вычислительной эквивалентности задач оптимизации и соответствующих им задач распознавания (принятия решений), в частности для задачи коммивояжёра.

[Sender]

Не уверен, что именно для задачи коммивояжёра в оптимизационной постановке доказана NP-лёгкость. А так Гэри, Джонсона прочитали уже? "Вычислительные машины и труднорешаемые задачи".

[technocrator]

Sender в сообщении #1503767 писал(а):

А так Гэри, Джонсона прочитали уже? "Вычислительные машины и труднорешаемые задачи".

естественно, в первую очередь глянул, но там теория именно для задач распознавания.

[Sender]

Хотя, с другой стороны, если у нас все веса рёбер целые... Пусть у нас есть $n$ вершин, а вес каждого ребра записывается не более, чем $d$-значным двоичным числом. Можете дать верхнюю оценку сложности алгоритма задачи коммивояжёра в оптимизационной постановке, если мы умеем решать её в постановке распознавания свойств(сложность в такой постановке можно считать известной)?

[technocrator]

Sender, я не хочу велосипед изобретать, хочу найти примеры литературы с формулировками обоснования )

[Sender]

technocrator, да бросьте, какой велосипед. Скорее, авторы посчитали этот вопрос настолько очевидным, что даже не сочли нужным его затрагивать.

[technocrator]

Расширение теории NP-сложности на оптимизационные задачи не столь очевидно хотя бы по причине того, что класс NP неформально описывается как "возможно, трудно решить, но решение всегда можно быстро проверить", в то время как для допустимого решения оптимизационной задачи, по-видимому, проверка на оптимальность так же трудна - что считать аналогом подсказки/оракула?

[Sender]

Ну раз мы пытаемся свести оптимизационную задачу к задаче распознавания, то, по-моему, вполне естественно вот эту последнюю и использовать в качестве оракула, нет?

[technocrator]

Мне не нужны догадки, нужны ссылки на то, как это описывается в теории сложности )

[offtop] Кстати, "NP-лёгкость" это существующий термин или какой-то жаргонизм?

[Sender]

technocrator в сообщении #1503830 писал(а):

Мне не нужны догадки, нужны ссылки на то, как это описывается в теории сложности )

К сожалению, тут ничем помочь не могу, не настолько глубоко в этой теме.

technocrator в сообщении #1503830 писал(а):

[offtop] Кстати, "NP-лёгкость" это существующий термин или какой-то жаргонизм?

Мне он встречался на лекциях, так что не думаю, что жаргонизм.

[technocrator]

Sender в сообщении #1503838 писал(а):

Мне он встречался на лекциях, так что не думаю, что жаргонизм.

И какие задачи этим словом описываются?

[Sender]

Насколько помню, те, что полиномиально сводятся к задачам из класса NP.

[пианист]

Эм. А разве класс NP не замкнут относительно полиномиальной сводимости?
Ни разу не специалист в теории сложности, если что

[Sender]

пианист в сообщении #1503846 писал(а):

А разве класс NP не замкнут относительно полиномиальной сводимости?

Ну так речь о задаче, чья принадлежность классу NP, исходя из условия, не установлена. Можете указать сертификат для задачи коммивояжёра в оптимизационной постановке?

[Xaositect]

technocrator в сообщении #1503766 писал(а):

Напомните примеры литературы, где подробно разбирается вопрос вычислительной эквивалентности задач оптимизации и соответствующих им задач распознавания (принятия решений), в частности для задачи коммивояжёра.

G. Aussiello, P. Crescenzi et al. Complexity and Approximation: Combinatorial optimization problems and their approximability properties. Springer, 1999. Chapter 1. The Complexity of Optimization Problems.

-- Вт фев 02, 2021 13:13:57 --

NP-easy это задачи, которые сводятся к задачам из NP (т.е. по сути к SAT), но во-первых, не обязательно задачи распознавания, и во-вторых, сводимость не по Карпу как в определении NP-полноты, а по Куку (с оракулом). То есть NP-легкие задачи это $\mathbf{FP}^{\mathbf{NP}}$.

-- Вт фев 02, 2021 13:21:00 --

technocrator в сообщении #1503816 писал(а):

Расширение теории NP-сложности на оптимизационные задачи не столь очевидно хотя бы по причине того, что класс NP неформально описывается как "возможно, трудно решить, но решение всегда можно быстро проверить", в то время как для допустимого решения оптимизационной задачи, по-видимому, проверка на оптимальность так же трудна - что считать аналогом подсказки/оракула?

Это правда, проверка на оптимальность для задачи оптимизации, у которой соответствующая задача распознавания лежит в NP, может быть полной для $\Delta_2^P$ (что, в прочем, все равно NP-easy). См. M. W. Krentel "The Complexity of Optimization Problems".