Если известно, что задача X (проблема решения) является NP-полной и доказано, что она сводится к проблеме Y, можете ли вы сказать, что проблема Y является NP-полной?

Question

Если известно, что задача X (проблема решения) является NP-полной и доказано, что она сводится к проблеме Y за полиномиальное время, то можете ли вы сказать, что задача Y является NP-полной?

Моей первой мыслью было, нет, нужно показать проблему Y, что она есть в NP. Но после дальнейших размышлений, если X уменьшается до Y, Y уже считается NP-завершенным. Теперь я просто растерялся ... любая помощь будет оценена.

Answer 1

Проблема X - Не уверен
Проблема Y - В NP

Чтобы доказать, что X в NP, вы показываете, что можете выполнить шаги, чтобы свести каждую проблему в X к проблеме в Y. Тогда вы знаете,что проблема X, по крайней мере, так же сложна, как и проблема Y.

Так что нет, вам нужно начать с Y, а затем уменьшить до X.

Answer 2

Аргументум на контраст:

Если X ∈ NP и X ⇔ Y и Y ∉ NP, то X ∉ NP.

Answer 3

Пока нет, вам понадобится еще несколько шагов

Чтобы доказать, что задача L является NP-полной, нам нужно выполнить следующие шаги:

1. Докажите, что ваша проблема L принадлежит NP (то есть при наличии решения вы можете проверить его за полиномиальное время)
2. Выберите известную NP-полную задачу L '
3. Опишите алгоритм f, который преобразует L 'в L
4. Докажите, что ваш алгоритм корректен (формально: x ∈ L 'тогда и только тогда, когда f (x) ∈ L)
5. Докажите, что алгоритм f работает за полиномиальное время

Пока у вас есть шаг 2,3,4
Вам все еще нужно показать, что сокращение является полиномиальным (шаг 5)
И что проблема принадлежит NP (шаг 1), то есть решение можно проверить за полиномиальное время.

Answer 4

Да, это правильно. Вы можете свести свою проблему за полиномиальное время к любой уже известной полной проблеме NP, но это считается очень сложной задачей. Таким образом, вместо этого вы выбираете уже завершенную проблему NP и сводите ее к своей проблеме, а также показываете, что она есть в NP, тогда ваша задача будет NP завершена.

Answer 5

SAT может быть решена за один вызов ALL, но это не означает, что ALL находится в NP.