É uma versão "local" do 3-SAT NP-hard?

7

Abaixo está minha simplificação de parte de um projeto de pesquisa maior sobre redes espaciais bayesianas:

Digamos que uma variável seja " -local" em uma string se houver menos de cláusulas entre a primeira e a última cláusula em que ela aparece (onde é um número natural).kC3-CNFkk

Agora considere o subconjunto definido pelo critério de que para qualquer , todas as variáveis ​​em é . Para que (se houver) é NP-difícil?(3,k)-LSAT3-SATC(3,k)-LSATCkk(3,k)-LSAT


Aqui está o que eu considerei até agora:

(1) Variações no método de mostrar que está em P reescrevendo cada disjunção como uma implicação e examinando caminhos direcionados no gráfico direcionado dessas implicações (anotados aqui e apresentados em detalhes nas pág. 184- 185 da Complexidade Computacional de Papadimitriou ). Diferentemente de , há ramificação dos caminhos direcionados em , mas talvez o número de caminhos direcionados seja limitado pelas restrições espaciais nas variáveis. Até agora, não houve sucesso com isso.2-SAT2-SAT(3,k)-LSAT

(2) Uma redução no tempo polinomial de (ou outro problema conhecido de NP-complete) para . Por exemplo, eu tentei vários esquemas de introdução de novas variáveis. No entanto, reunir as cláusulas que contêm a variável original geralmente exige que eu arraste "cadeias" de cláusulas adicionais contendo as novas variáveis ​​e elas interfiram nas restrições espaciais das outras variáveis.3-SAT(3,k)-LSATxk

Certamente não estou em um novo território aqui. Existe um problema NP-hard conhecido que pode ser reduzido para ou as restrições espaciais impedem que o problema seja tão difícil?(3,k)-LSAT

SapereAude
fonte

Respostas:

13

(3,k)-LSAT está em P para todos os . Como você indicou, a localidade é uma grande obstrução à completude da PN.k


Aqui está um algoritmo polinomial.

Entrada: , , em que é a ésima cláusula. Saída: true se se torna 1 sob alguma atribuição de todas as variáveis. Procedimento:ϕ(3,k)-LSATϕ=c1c2cmcii
ϕ

  1. Construa o conjunto , as variáveis ​​que aparecem em pelo menos uma de , .Bici,ci+1,,ci+k1imk
  2. O conjunto de construções .Ai={f:Bi{0,1}ci,ci+1,,ci+k become 1 underf}
  3. Conjunto de construçõesE=i{(f,g)fAi,gAi+1,f(x)=g(x) for all xBiBi+1}
  4. Seja . Considere o gráfico direcionado . Para cada vértice em , inicie uma pesquisa profunda em para ver se conseguimos alcançar um vértice em . Se encontrado, retorne verdadeiro.V=A1A2AmkG(V,E)A1GAmk
  5. Se chegamos aqui, retorne false.

A correção do algoritmo acima vem da seguinte reivindicação.

Afirmação. é satisfatório existe um caminho em de um vértice em para um vértice em . Prova. " ": suponha que se torne 1 na atribuição . Seja a restrição de para . Então temos o caminho . " ": suponha que exista um caminho , em que e . Definir atribuiçãoϕGA1Amk

ϕffifBif1,,fmk
f1,,fmkf1A1fmkAmkf tal que concorda com todos os , ou seja, se . Podemos verificar que está bem definido. Como se torna 1 para alguns para todos , se torna 1 em .ffif(x)=fi(x)xBifcfjϕf


O número de vértices . Por isso o algoritmo é executado em tempo polinomial em termos de , o número de cláusulas e , o número de variáveis no total.|V|23(k+1)(mk)mn

John L.
fonte
Na etapa 4, "para cada vértice em " deve ser melhor "de cada vértice em ". A1A1
John L.
Este método é realmente útil. Estou envergonhado por não o ter visto antes da sua postagem. Você conhece uma referência (livro, artigo, etc.) onde ela aparece?
Sapere Aude
11
Receio não me lembrar de nenhuma referência direta. No entanto, é um tema importante em matemática que uma solução global possa ser montada a partir de soluções locais às vezes.
John L.