Seja as variáveis . A distância entre duas variáveis é definida como d ( x a , x b ) = | a - b | . A distância entre dois literais é a distância entre as duas variáveis correspondentes.
Suponha que eu tenha uma instância 3-SAT, de modo que, para cada cláusula , tenhamos d ( x a , x b ) ≤ N ∧ d ( x a , x c ) ≤ N ∧ d ( x b , x c ) ≤ N para algum valor fixo N .
Conceitualmente, você pode imaginar isso como todos os literais estando fisicamente em uma linha e todas as cláusulas são incapazes de atingir além de um determinado comprimento por razões físicas.
Dada essa restrição, existem instâncias rígidas do 3-SAT? Quão pequeno posso tornar a vizinhança e ainda encontrar instâncias difíceis? E se eu permitir que algumas cláusulas violem a restrição?
Por difícil, quero dizer que um solucionador heurístico se voltaria ao pior caso.
fonte
Respostas:
Não. Se a instância 3-SAT possui cláusulas, você pode testar a satisfação em tempo de O ( m 2 N ) . Desde Nm O(m2N) N é uma constante fixa, esse é um algoritmo de tempo polinomial que resolve todas as instâncias do seu problema.
O algoritmo funciona em estágios. Deixe φ i denotar a fórmula que consiste das cláusulas que utilizam apenas a partir de variáveis x 1 , ... , x i . Seja S i ⊆ { 0 , 1 } n denota o conjunto de atribuições para x i - N , x i - N + 1 , … , x i que pode ser estendido a uma atribuição satisfatória para φ i . Note que dado Sm φi x1,…,xi Si⊆{0,1}n xi−N,xi−N+1,…,xi φi , podemos calcularSi−1 no tempo O ( 2 N ) : para cada ( x i - N - 1 , … , x i - 1 ) ∈ S i - 1 , tentamos ambas as possibilidades para x i e verificamos se satisfaz todas as cláusulas de φ i que contêm a variável x i ; nesse caso, adicionamos ( x i - N , …Si O(2N) (xi−N−1,…,xi−1)∈Si−1 xi φi xi a S i . Noi(xi−N,…,xi) Si i th palco, calculamos . Depois de concluir todos os m estágios, a instância 3-SAT é satisfatória se e somente se S m ≠ ∅ . Cada estágio leva tempo O ( 2 N ) e há m estágios, portanto, o tempo total de execução é O ( m 2 N ) . Isso é polinomial no tamanho da entrada e, portanto, constitui um algoritmo de tempo polinomial.Si m Sm≠∅ O(2N) m O(m2N)
fonte
O gráfico de incidentes de uma fórmula SAT é um gráfico bipartido que possui um vértice para cada cláusula e cada variável. Adicionamos arestas entre uma cláusula e todas as suas variáveis. Se o gráfico de incidentes limitou a largura da árvore, podemos decidir a fórmula SAT em P, na verdade, podemos fazer muito mais. Seu gráfico de incidentes é muito restrito. Por exemplo, é um gráfico de largura de caminho limitado, portanto é polinomial solucionável em tempo. Para o resultado estrutural bem conhecido acima, por exemplo, consulte: https://www.sciencedirect.com/science/article/pii/S0166218X07004106 .
fonte