Eu sei pelo Teorema da Dicotomia de Schaefer que apenas alguns tipos de problemas de satisfação estão em P e qualquer outro problema é NP-completo. No entanto, todos os algoritmos que eu conheço usam técnicas específicas únicas para esse tipo de problema - por exemplo, propagação de unidade para Hornsat, técnicas algébricas lineares mod 2 para XORSAT e várias outras técnicas para 2-sat. Existe um algoritmo polytime geral que funciona para todos esses problemas em P? Obrigado.
7
Respostas:
O teorema da dicotomia de Schaefer é comprovado dividindo os CSPs em dois tipos: aqueles que podem ser reduzidos a um dos poucos problemas específicos em P e o outro no qual o SAT pode ser reduzido (e o NP completo). Especificamente, todo CSP do tipo anterior é trivial (sempre satisfeito pela atribuição constante de 0 ou constante 1), pode ser reduzido para 2SAT, reduzido para HORN-SAT ou reduzido para XOR-SAT. Esses são os únicos algoritmos necessários para resolver esses CSPs. Não existe um único algoritmo - existe uma lista finita de algoritmos.
fonte
Procure papéis / livros escritos por Vijay Chandru, John Hooker e John Franco. Algumas de suas técnicas usam Programação Inteira (observando estruturas especiais na matriz gerada pelas cláusulas CNF da instância SAT). As fórmulas de "chifre estendido" têm uma estrutura especial quando representadas como gráficos que as tornam polinomialmente solucionáveis.
Para citar Franco em sua pesquisa de 2009: O leitor pode ter a impressão de que o número de classes solucionáveis no tempo polinomial é bastante pequeno devido ao famoso teorema da dicotomia de Schaefer. Mas esse não é o caso. Schaefer propôs um esquema para definir classes de expressões proposicionais com uma noção generalizada de "cláusula". Ele provou que todas as classes definíveis em seu esquema eram solucionáveis em tempo-NP completo ou polinomial e deu critérios para determinar quais. Mas nem todas as classes podem ser definidas dentro de seu esquema. As classes Horn e XOR podem ser, mas descreveremos várias outras, incluindo q-Horn, Horn estendido, CC-balance e SLUR que não podem ser assim definidos. O motivo é que o esquema de Schaefer é limitado a classes que podem ser reconhecidas no espaço de log .
fonte