Existem instâncias difíceis do 3-SAT quando as cláusulas podem usar apenas literais que estão "próximos" um do outro?

22

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.x1,x2,x3...xnd(xa,xb)=|ab|

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 .(xa,xb,xc)d(xa,xb)Nd(xa,xc)Nd(xb,xc)NN

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.

IIAOPSW
fonte
2
"Com muita força, quero dizer que um solucionador heurístico voltará ao pior caso". não parece bem definido para mim. Podemos interpretar sua pergunta perguntando se existe um algoritmo de tempo polinomial que resolva todas essas instâncias 3-SAT? Ou perguntando sobre a complexidade / dureza deste problema?
DW
"Podemos interpretar sua pergunta perguntando se existe um algoritmo de tempo polinomial que resolva todas essas instâncias de 3-SAT?" Eu acho que é isso que estou procurando.
IIAOPSW
1
O requisito de localidade que você está usando também é conhecido como 1D "geometricamente local" e é o significado predominante de "localidade" para os físicos. Agora, se alguém generaliza sua pergunta para o caso quântico e de bits (2 estados) para partículas com 8 estados, a versão quântica do seu problema é realmente QMA-complete ("quantum-NP") em 1D: Veja arxiv.org/ abs / 1312.1469 Para qubits, o problema é completo com QMA em 2D. arxiv.org/abs/quant-ph/0504050
Martin Schwarz
4
Ah, então é verdade que um físico não pode se esconder entre os cientistas da computação. Você me pegou. Por que você precisa de 8 estados? Basta usar qubits, triplicar o tamanho da vizinhança e usar a cada 3 qubits para codificar uma partícula de 8 estados.
IIAOPSW
1
Claro, mas você tem uma localidade bastante alta, ou seja, seus operadores locais abrangem muitos qubits. Essa linha de pesquisa também se concentrou em minimizar a localidade (idealmente 2-local) ao custo de partículas com dimensões mais altas e as compensações envolvidas.
Martin Schwarz

Respostas:

30

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 NmO(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φix1,,xiSi{0,1}nxiN,xiN+1,,xiφi , podemos calcularSi1 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 , SiO(2N)(xiN1,,xi1)Si1xiφixia S i . Noi(xiN,,xi)Sii 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.SimSmO(2N)mO(m2N)

tO(m2(t+1)N)t

DW
fonte
16

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 .

Saeed
fonte
1
Na verdade, mesmo o gráfico primitivo (uma aresta entre dois vértices, se eles aparecerem na mesma cláusula) limitou a largura de caminho nesse caso. Veja também (1) que pode ser mais acessível ou a resposta @DW, que é aproximadamente a mesma idéia que esses algoritmos. (1) Algoritmos para contagem de modelos proposicionais , Marko Samer, Stefan Szeider, J. Algoritmos Discretos, volume 8, número 1, páginas 50-64, 2010.
holf