Satisfacción sábada con 10 variables.

Question

Estoy tratando de probar que el siguiente problema es NPC:

$$ A={\ langle \ phi \ rangle \ \ big |\ \ Phi \ \ Text {es CNF y se ha sentado.asignación donde exactamente 10 vars son verdaderas} \} $$

Estoy tratando de encontrar una reducción de mapeo polinomial de SAT, pero no puedo encontrar una manera de forzar exactamente 10 variables para obtener una tarea verdadera. Mi idea era crear una nueva fórmula, con 10 cláusulas, cada cláusula es la intersección de una nueva variable $ x_i $ con la fórmula antigua, pero no veo cómoMi idea útil.

Apreciaría la ayuda.

Answer 1

El problema que mencionó está en $ P $ por lo que no es NP-completo.Sabemos que $ | \ phi |= n $ por lo que el número de variables es menor que $ n $ y sabemos que los miembros de $ a$ tiene 10 tareas verdaderas.Por lo tanto, por un algoritmo de la fuerza bruta, compruebe cada asignación posible a las variables.Elija 10 variables de n, $ (^ {n} _ {10}) $ y configúrelos en $ true $ y configura otras variables a $ falso $ y verifique si esta es una asignación satisfactoria.El tiempo de ejecución de este algoritmo es $ (^ {n} _ {10}) * n= o (n ^ {11}) $ .