SAT-Zufriedenheit mit 10 Variablen

Question

Ich versuche zu beweisen, dass das nächste Problem NPC ist:

$$ A=\ \ \ Langle \ phi \ Rangle \ \ Big |\ \ phi \ \ Text {ist CNF und hat Sat.Zuordnung, bei der genau 10 Vars true sind} \} $$

Ich versuche, die Reduzierung der Polynomabbildung von SAT zu finden, aber ich kann keinen Weg finden, genau 10 Variablen zu zwingen, um wahre Aufgabe zu erzielen. Meine Idee war, eine neue Formel zu erstellen, mit 10 Klauseln, jeder Klausel ist die Kreuzung einer neuen Variablen $ x_i $ mit der alten Formel, aber ich sehe nicht, wieMeine Idee hilfreich.

Ich würde helfen, Hilfe zu schätzen.

Answer 1

Das von Ihnen erwähnte Problem ist in $ P $ , daher ist es nicht np-komplett.Wir wissen, dass $ | \ phi |= n $ Daher ist die Anzahl der Variablen weniger als $ N $ und wir wissen, dass Mitglieder von $ a$ Genau haben 10 wahre Aufgaben.Überprüfen Sie also mit einem Brute-Force-Algorithmus jede mögliche Zuordnung zu Variablen.Wählen Sie 10 Variablen aus n, $ (^ {n} _ {10}) $ und legen Sie sie auf $ true $ und setze andere Variablen auf $ false $ und überprüfen, ob dies eine erfüllende Aufgabe ist.Die Laufzeit dieses Algorithmus ist $ (^ {n} _ {10}) * n= o (n ^ {~ 11}) $ .