10 변수로 만족스럽게 앉았습니다

Question

다음 문제가 NPC 인 것임을 증명하려고합니다.

$$ A={\ langle \ phi \ rangle \ \ big |\ \ phi \ \ text {CNF이며 SAT가 있습니다.정확히 10 vars가 true} \} 인 할당 $$

SAT에서 다항식 매핑 감소를 찾으려고 노력하고 있지만 정확히 10 변수를 강제로 할 수있는 방법을 찾을 수 없습니다. 내 아이디어는 10 개의 클로스가있는 새 공식을 만드는 것이 었습니다. 각 절은 새로운 수식으로 새로운 변수 $ X_I $ 의 교차점이지만 어떻게 보이지 않게 보이지 않습니다.내 생각이 도움이됩니다.

도움을 주셔서 감사합니다.

Answer 1

언급 한 문제점은 $ P $ 이므로 NP 완료가 아닙니다.우리는 $ | \ phi |= n $ 이므로 변수의 수는 $ n $ 보다 작으며 $ a$ 정확히 10 개의 진정한 과제가 있습니다.그래서 무차별 힘 알고리즘은 모든 가능한 할당을 변수에 검사합니다.n, $ (^ {n} _ _ {10})로부터 $ true $ 다른 변수를 $ false $ 에 설정하고 이것이 만족스러운 과제인지 확인하십시오.이 알고리즘의 런타임은 $ (^ {n} _ _ {10}) * n= o (n ^ {11}) $