Elberfeld, Jakoby e Tantau 2010 ( ECCC TR10-062 ) provaram ser uma versão com eficiência de espaço do teorema de Bodlaender. Eles mostraram que para gráficos com largura de árvore no máximo , pode-se encontrar uma decomposição em árvore da largura usando espaço logarítmico. O fator constante no espaço limitado depende de . (O teorema de Bodlaender mostra um limite linear no tempo, com uma dependência exponencial de no fator constante.)k k k
O SAT se torna fácil quando o conjunto de cláusulas tem baixa largura. Especificamente, Fischer, Makowsky e Ravve 2008 mostraram que a satisfação das fórmulas de CNF com a largura da árvore do gráfico de incidência delimitada por pode ser decidida com no máximo operações aritméticas quando a decomposição da árvore é dada. Pelo teorema de Bodlaender, o cálculo da decomposição em árvore do gráfico de incidência para fixo pode ser feito em tempo linear e, portanto, o SAT pode ser decidido para fórmulas limitadas de largura de árvore no tempo que é um polinômio de baixo grau no número de variáveis .2 O ( k ) n k n
Pode-se então esperar que o SAT seja realmente decidível usando espaço logarítmico, para fórmulas com largura de árvore limitada do gráfico de incidência. Não está claro como modificar Fischer et al. abordagem para decidir SAT em algo eficiente em termos de espaço. O algoritmo funciona computando uma expressão para o número de soluções, via inclusão-exclusão e avaliando recursivamente o número de soluções de fórmulas menores. Embora a largura da árvore delimitada ajude, as subfórmulas parecem ser muito grandes para serem computadas no espaço logarítmico.
Isso me leva a perguntar:
Sabe-se que SAT para fórmulas de largura de árvore limitada está em ou ?N L
fonte
Respostas:
De fato, usando os resultados de Elberfeld-Jakoby-Tantau-2010, pode-se mostrar que o SAT pode ser decidido no espaço de log em fórmulas cujo gráfico de incidência delimitou a largura da árvore. Aqui está um esboço de como vão as principais etapas da prova desta reivindicação.
fonte