problemas de implementação em 2-satisfatibilidade problema

Question

Eu quero implementar problema 2-SAT para 100000 literais. Assim, não haveria 200000 vértices. Então, eu estou preso em ter uma matriz de todos os vértices alcançáveis ??a partir de cada vértice, a complexidade do espaço de O(200000^2) que é inviável Então, por favor sugerir uma solução para isso. E, por favor lançar alguma luz sobre a implementação eficiente do problema 2-sáb.

Answer 1

A partir wikipedia :

... 2-satisfatibilidade pode ser resolvido em tempo polinomial. Como Aspvall, Plass & Tarjan (1979) observado, um exemplo 2-satisfazibilidade é solúvel se e apenas se todas as variáveis ??do exemplo pertence a um componente fortemente ligado diferente do gráfico implicação do que a negação da mesma variável. Desde componentes fortemente conectados podem ser encontradas em tempo linear por um algoritmo baseado na busca em profundidade, ao mesmo tempo linear ligada aplica-se também a 2-satisfatibilidade.

Eu não vou fingir que entendo mais do mesmo número, mas parece que há é um algoritmo que pode ser usado para resolver o problema 2-SAT, e é descrito dentro desse referenciada documento ( Um algoritmo linear de tempo para testar a verdade de certos quantificada boolean fórmulas ). Ele aparentemente pode ser comprado on-line para cerca de US $ 20 USD. Eu não tenho certeza se isso é útil ou não, mas não é!

atualização: A PDF livre do mesmo documento pode ser encontrado aqui . O crédito vai para Liori para a descoberta.

Answer 2

Toda Esta discussão é um pouco confuso. Sim, pode-se resolver 2-sentou em tempo linear, mas nenhum - você não pode resolvê-lo para que muitas variáveis. O tempo para resolver 2-sat é linear em relação ao número de implicação, que por 200 000 variáveis ??poderiam chegar a até (200000 * 199999) / 2 e, além disso, se você usar esta solução terá aproximadamente a mesma quantidade de memória . Não há outra solução (sem uso de componentes fortemente ligados que seja mais lento, mas não precisa que muita memória).