k-SAT — это частный случай SAT. Поскольку SAT является NP-полным, я не понимаю, почему у нас нет k-SAT, являющегося NP-полным для любых значений k. На занятии мой профессор использовал полиномиальную редукцию из SAT, чтобы доказать, что 3-SAT является NP-полным. Я не понимаю, почему мы должны доказывать это, разве частный случай не должен следовать правилу для общего случая?
SAT является NP-полным, так почему бы нам не k-SAT является NP-полным для произвольного значения k?
Ответы (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-полным и, таким образом, создает хорошую основу для сведения к нему других проблем. Надеюсь, это поможет!
person
alias
schedule
21.04.2020
спасибо за указание на случаи 1-SAT и 2-SAT. Это имеет смысл. Но я еще не совсем понимаю 3-SAT. В нашем классе нам дано, что CNF-SAT является NP-полным. Чтобы доказать, что 3-SAT также является NP-полным, мой профессор сократил CNF-SAT до 3-SAT. Это означает, что 3-SAT не менее сложен, чем CNF-SAT. Это контрастирует с моей интуицией, что 3-SAT — это простейший случай общего SAT.
- person old man; 21.04.2020
Думайте о простейшем в этом предложении как о наименьшем k таком, что оно является NP-полным. Таким образом, 4-SAT, 5-SAT и т. д. так же сложны, как 3-SAT, просто так получилось, что 3-SAT является самым простым, потому что он является самым ограничивающим в этом семействе. В противном случае все они являются NP-полными, что буквально означает, что решение одного за полиномиальное время решит все остальные. Так что в этом смысле все они одинаково просты и/или сложны, пока k›=3.
- person alias; 21.04.2020
