O Quase-2-SAT NP é difícil?

10

Um problema CNF SAT NP é difícil quando o número total (mas não a largura) das cláusulas de 3 ou mais termos é delimitado acima por uma constante? Que tal especificamente quando existe apenas uma dessas cláusulas?

np-hardness sat upper-bounds dspyz
fonte

8

Se houver apenas uma tal cláusula com mais do que 2 termos, resolver tais fórmulas é trivialmente em . Se tiver termos, tente cada uma das designações parciais que satisfazem e resolva a fórmula 2-SAT restante usando o método de tempo linear conhecido. Eventualmente, você encontrará uma solução para toda a fórmula ou provará que ela é insatisfatória em , em que não pode exceder o número de variáveis na fórmula inteira.

c

$c$

P

$P$

c

$c$

n

$n$

n

$n$

c

$c$

O (n^{2})

$O(n^2)$

n

$n$

Kyle Jones

@KyleJones Mas uma única cláusula com literais tem tarefas satisfatórias, não apenas . Como não está delimitado na pergunta, essa abordagem fornece um algoritmo de tempo exponencial.

k

$k$

2^{k} - 1

$2^k-1$

k

$k$

k

$k$

David Richerby

2

@DavidRicherby Para satisfazer a cláusula, você só precisa fazer um dos literais avaliar true. Depois disso, a cláusula poderá ser ignorada e você só terá uma fórmula 2-SAT. literais significa que você só precisa tentar atribuições.

k

$k$

k

$k$

Kyle Jones

14

Vale ressaltar que o problema se torna difícil para NP quando a restrição é relaxada um pouco.

Com um número fixo de cláusulas que também são de tamanho limitado, o número médio de literais em uma cláusula é tão próximo de 2 quanto se deseja, considerando uma instância com variáveis suficientes. Como você aponta, existe um limite superior simples que é polinomial se o tamanho da cláusula for delimitado.

Por outro lado, se o número médio de literais por cláusula for pelo menos para alguns fixos (mas arbitrariamente pequenos) , o problema é difícil para o NP. $2 + \epsilon$ $\epsilon > 0$

Isso pode ser mostrado reduzindo o 3SAT a esse problema, introduzindo novas cláusulas com 2 literais que são trivialmente satisfatórios. Suponha que haja cláusulas na instância 3SAT; para reduzir o tamanho médio da cláusula para , basta adicionar novas cláusulas com duas literais. Como é fixo e positivo, a nova instância é de tamanho polinomial. $m$ $(2+\epsilon)$ $m(1 - \epsilon)/\epsilon$ $\epsilon$

Essa redução também mostra que mesmo a versão em que as cláusulas "grandes" estão restritas a 3 literais é difícil para o NP.

O caso restante é quando as poucas cláusulas grandes não são de tamanho limitado; cada cláusula grande parece dificultar o problema. Veja o artigo da SODA 2010 de Pǎtraşcu e Williams para o caso de duas cláusulas: eles argumentam que se isso puder ser feito em tempo sub-quadrático, teríamos melhores algoritmos para o SAT. Pode haver uma extensão de seu argumento para mais cláusulas, o que forneceria evidências de que seu limite superior não pode ser melhorado (módulo alguma forma da hipótese do tempo exponencial).

András Salamon
fonte

apenas tangencialmente relacionados, mas há um papel ECCC recente que formula "quase 2-SAT" de uma maneira diferente e prova dureza forte: eccc.hpi-web.de/report/2013/159

Sasho Nikolov

8

OK, entendi. A resposta é não. Isso pode ser resolvido em poli-tempo. Para cada cláusula de 3 ou mais termos, selecione um literal e defina-o como verdadeiro. Em seguida, solucione o problema restante de 2 sat. Se alguém fornecer uma solução, essa é uma solução para o problema geral. Como o número de cláusulas de 3 ou mais termos é fixo (digamos c), se todas essas cláusulas tiverem tamanho <= m, isso será executado em O (m ^ (c) * n). O (m ^ c) para percorrer cada seleção possível, vezes O (n) para resolver o problema restante de 2 sat.

dspyz
fonte

m

$m$

É porque m é implicitamente limitado pelo número de átomos. Obviamente, uma cláusula não pode ter mais literais do que átomos no problema. Talvez eu devesse ter esclarecido m <= n

dspyz

O Quase-2-SAT NP é difícil?

Respostas: