Estou interessado em uma variação de SAT em que a fórmula CNF é monótona (nenhuma variável é negada). Essa fórmula é obviamente satisfatória.
Mas digamos que o número de variáveis verdadeiras seja uma medida de quão boa é a nossa solução. Portanto, temos o seguinte problema:
MONOTONE VERDADEIRO MÍNIMO 3SAT
INSTANCE: Define U de variáveis, coleção C de cláusulas disjuntivas de 3 literais, onde um literal é uma variável (não negada).
SOLUÇÃO: Uma atribuição de verdade para U que satisfaça C.
MEDIDA: O número de variáveis verdadeiras.
Alguém poderia me dar algumas observações úteis sobre esse problema?
fonte
fonte