SAT является NP-завершенным, так почему бы нам не сделать k-SAT-NP завершенным для произвольного значения k?

Question

k-SAT является частным случаем SAT. Так как SAT является NP-полной, я не понимаю, почему у нас нет k-SAT является NP-полной для любых значений k. В классе мой профессор использовал полиномиальное сокращение от SAT, чтобы доказать, что 3-SAT является NP-полной. Я не понимаю, почему мы должны доказывать это, разве не должен особый случай следовать правилу общего случая?

Answer 1

Что ж, ваша заявка явно не соответствует действительности для 1- или 2-SAT.

1-SAT-проблема (т. Е. Когда у вас есть не более одного литерала!), Очевидно, линейна по числу предложений и переменные, так как полярность в каждом пункте скажет вам, как выбирать переменные.

2-SAT сложнее, но вы можете решить это за полиномиальное время: https://www.geeksforgeeks.org/2-satisfiability-2-sat-problem/

Для любого k > 3 k -SAT, очевидно, NP-завершен; поскольку любой алгоритм для них может быть использован для решения 3-SAT, как, по-видимому, обсуждал ваш профессор.

Итак, фундаментальная путаница здесь заключается в том, что хотя k -SAT является примером общая проблема SAT не означает, что все проблемы k -SAT одинаково трудны. В некотором смысле, 3-SAT является «самым простым» экземпляром SAT, который является NP-полным и, таким образом, служит хорошей основой для решения других проблем. Надеюсь, это поможет!