2-satisfatibilidade problema-Se uma atribuição única verdade existe ou não

Question

Eu tenho um problema que é uma extensão do problema 2-sáb. No padrão problema 2-SAT, podemos encontrar qualquer uma das atribuições verdade que depende a ordenação de vértices que escolhemos. Quero verificar se existe uma e apenas uma atribuição verdade (isto é, apenas uma combinação) para o qual a expressão é satisfeita. O número de literais pode ser 100000. Uma maneira é encontrar todas as possíveis atribuições de verdade, então compará-los se eles são distintos. Mas o problema é para cada comparação, vou ter que comparar 100000 valores (não de literais). Existe alguma maneira eficiente?

Answer 1

Feder (1994) descreve um algoritmo para listar de forma eficiente todas as soluções para um determinado 2 satisfazibilidade exemplo . Há também citações no artigo para algoritmos para contar o número de atribuições, mas você só precisa tentar listando dois trabalhos, o que pode ser mais eficiente.