SAT удовлетворение 10 переменными

Question

Я пытаюсь доказать, что следующая проблема - NPC:

$$ A={\ langle \ phi \ Rangle \ \ big |\ \ phi \ \ Text {CNF и сидел.Назначение, где ровно 10 варс верно} \} $$

Я пытаюсь найти сокращение полиномиального сопоставления от SAT, но я не могу найти способ заставить ровно 10 переменных, чтобы получить истинное задание. Моя идея состояла в том, чтобы создать новую формулу, с 10 пунктами, каждый пункт является пересечением новой переменной $ X_I $ со старой формулой, но я не вижу, какМоя идея полезно.

Я буду признателен за помощью.

Answer 1

Указанная вами проблема находится в $ P $ Так что это не NP-завершение.Мы знаем, что $ | \ phi |= n $ Так что количество переменных меньше, чем $ n $ , и мы знаем, что члены $ A$ именно имеет 10 истинных заданий.Так что по алгоритму грубой силы проверяйте все возможное задание переменным.Выберите 10 переменных от n, $ (^ {n} _ {10}) $ и установите их на $ true $ и установите другие переменные на $ false $ и проверьте, является ли это удовлетворение.Время выполнения этого алгоритма является $ (^ {n} _ {10}) * n= o (n ^ {11}) $ .