Sat satisfação com 10 variáveis

Question

Eu estou tentando provar que o próximo problema é NPC:

$$ A={\ langle \ phi \ rangle \ big |\ \ phi \ \ text {is cnf e sentou-se.Atribuição onde exatamente 10 vars são verdadeiros}} $$

Eu estou tentando encontrar redução de mapeamento polinomial de SAT, mas não consigo encontrar uma maneira de forçar exatamente 10 variáveis para obter a tarefa verdadeira. Minha ideia era criar nova fórmula, com 10 cláusulas, cada cláusula é a interseção de uma nova variável $ x_i $ com a fórmula antiga, mas não vejo comominha ideia útil.

Eu apreciaria a ajuda.

Answer 1

O problema que você mencionou está em $ P $ por isso não é np-completo.Sabemos que $ | \ Phi |= n $ para que o número de variáveis seja menor que $ n $ e sabemos que membros da $ a$ Exatamente tem 10 atribuições verdadeiras.Assim, por um algoritmo de força bruta, verifique todas as tarefas possíveis para variáveis.Escolha 10 variáveis de n, $ (^ {n} _ {10}) $ e defina-os para $ TRUE $ e definir outras variáveis para $ false $ e verifique se esta é uma tarefa satisfatória.O tempo de execução deste algoritmo é $ (^ {n} _ {10}) * n= o (n ^ {11}) $ .