Моя книга утверждает это
- Если задача решения B находится в P, а A сводится к B, то проблема решения A находится в P.
- Решение задачи B является NP-полным, если B находится в NP, и для каждой задачи в A в NP, A сводится к B.
- Решающая задача C является NP-полной, если C находится в NP, а для некоторой NP-полной задачи B B уменьшается до C.
Так что мои вопросы
- Если B или C находится в NP-полной ситуации, и все проблемы в NP сводятся к проблеме NP-полной, используя первое правило, как любая проблема NP не может быть NP-полной?
- Если A уменьшается до B, B уменьшает до A?
complexity-theory
np-complete
decision-problem
rubixibuc
источник
источник
Ответы:
Нет. Для действительно надуманного примера любая возможная вычислимая проблема A сводится к проблеме останова: просто передайте в качестве входных данных алгоритм, который решает проблему A, но с
while(true)привязкой в конце после истинного или ложного случая. Тем не менее, мы знаем, что проблема Остановки не вычислима, поэтому она не может быть сведена к любому такому алгоритму А.Основная идея состоит в том, что если есть сокращение от A до B, вы можете узнать, что B, по крайней мере, так же трудно решить, чем A, и требует алгоритм, который, по крайней мере, такой же мощный.
Таким образом, если задача A сводится к простой задаче B, то мы можем легко вывести A (поскольку сокращение дает нам эффективный алгоритм), а если сложная задача A сведена к проблеме B, мы можем сделать вывод, что B также сложна ( так как если бы B было легко, то и A тоже должно быть легко). Однако все еще есть возможность сделать глупое сокращение от простой проблемы до сложной проблемы, но в этом случае мы не можем сделать какие-либо выводы.
источник
Первое правило касается проблем в P. Это не имеет никакого отношения к полноте NP. Если задача A является NP Complete, а проблема B сводится к A, это не означает, что B NP NP Complete.
Нет, вообще нет.
источник
У меня есть только основная идея относительно проблем NPC и NP. Но все, что я хочу прокомментировать, - это: «Если A уменьшается до B, то B уменьшается до A?»
Просто рассмотрим множество A, содержащее {2,3,4,5} элементов, и множество B, содержащее {3,4}. Таким образом, A можно уменьшить до B. Но B нельзя уменьшить до A. Вместо этого B можно расширить до A, если B получает {2,5} элементов.
Но если A и B имеют одинаковые. тогда A можно уменьшить до B или B можно уменьшить до A.
источник