O problema de decidir se um CNF monótono implica um DNF monótono

14

Considere o seguinte problema de decisão

Entrada : um CNF monótono Φ e um DNF monótono .Ψ

Pergunta : uma tautologia?ΦΨ

Definitivamente, você pode resolver esse problema no tempo , onde é o número de variáveis ​​em e é o comprimento da entrada. Por outro lado, esse problema é coNP-completo. Além disso, uma redução que estabelece a completação de coNP também mostra que, a menos que SETH falhe, não há algoritmo de tempo de para esse problema (isso vale para qualquer positivo ). Aqui está essa redução. Seja um CNF (não monótono) e seja sua variável. Substitua toda ocorrência positiva de porO(2npoly(l))nΦΨlO(2(1/2ε)npoly(l))εAxxye toda ocorrência negativa de por . Faça o mesmo para todas as variáveis. Seja o CNF monótono resultante como . É fácil perceber que é satisfatório se não é uma tautologia. Essa redução explode o número de variáveis ​​por um fator 2, o que implica em (limite baseado em SETH) mencionado acima.xzΦAΦyz2n/2

Portanto, existe um intervalo entre e time. Minha pergunta é se é conhecido algum algoritmo melhor ou melhor redução do SETH?2n/22n

Apenas duas observações aparentemente relacionadas ao problema:

  • um problema inverso de saber se um DNF monótono implica um CNF monótono é trivialmente solucionável em tempo polinomial.

  • Curiosamente, o problema de decidir se e calcula a mesma função pode ser resolvido em tempo quase polinomial devido a Fredman e Khachiyan (Sobre a complexidade da dualização de formas normais disjuntivas monótonas, Journal of Algorithms 21 (1996), não 3, pp. 618–628, doi: 10.1006 / jagm.1996.0062 )ΦΨ

Sasha Kozachinskiy
fonte

Respostas:

6

Assumindo SETH, o problema não é solucionável no tempo para qualquer ϵ > 0 .O(2(1-ϵ)npoeuy(eu))ϵ>0 0


Primeiro, deixe-me mostrar que isso é verdade para o problema mais geral em que e Ψ podem ser fórmulas monótonas arbitrárias. Nesse caso, há uma redução de ctt de politempo de TAUT para o problema que preserva o número de variáveis. Seja T n t ( x 0 , , x n - 1 ) denotar a função de limiar T n t ( x 0 , , x n - 1 ) = 1ΦΨTtn(x0 0,...,xn-1) Usando a rede Ajtai-Komlós-Szemerédi triagem,T n t pode ser escrito por uma fórmula monótona de tamanho polinomial, construtıvel em tempopoly(n).

Ttn(x0 0,...,xn-1)=1|{Eu<n:xEu=1}|t.
Ttnpoeuy(n)

Dada uma fórmula booleana , podemos usar as regras de De Morgan para escrevê-la no formato ϕ ( x 0 , , x n - 1 , ¬ x 0 , , ¬ x n - 1 ) , onde ϕ ' é monótono. Então ϕ ( x 0 , , x n -ϕ(x0 0,...,xn-1)

ϕ(x0 0,...,xn-1,¬x0 0,...,¬xn-1),
ϕé uma tautologia se e somente se as implicações monótonas T n t ( x 0 ,, x n - 1 ) ϕ ( x 0 ,, x n - 1 , N 0 ,, N n - 1 ) são válidos para cadatn, onde N i = T n - 1 t (ϕ(x0,,xn1)
Ttn(x0,,xn1)ϕ(x0,,xn1,N0,,Nn1)
tn
Ni=Ttn1(x0,,xi1,xi+1,,xn1).

eTtnteeteNEu¬xEueϕeϕ(x0 0,...,xn-1,N0 0,...,Nn-1)eϕ(x0 0,...,xn-1,N0 0,...,Nn-1)


2δnpoly(l)kkk2δn+O(knlogn)poly(l)δ1

k

ϕ=i<l(jAixjjBi¬xj),
|Ai|+|Bi|kinn=n/bbk1nlognϕ
()u<nTtub(xbu,,xb(u+1)1)i<l(jAixjjBiNj)
nt0,,tn1[0,b]j=bu+j0j<b
Nj=Ttub1(xbu,,xbu+j1,xbu+j+1,,xb(u+1)1).
TtbO(2b)()O(n2b)NjO(2b)O(2kb)O(l2kb)()O(l2O(kb))nO(2δn+O(kb)lO(1))bnt
O((b+1)n/b2δn+O(kb)lO(1))=O(2δn+O(knlogn)lO(1))

k3kΦkΨk

sk=inf{δ:k-SATDTIME(2δn)},s=sup{sk:k3}.
sk=inf{δ:k-MonEumpDTEuME(2δn)},s=sup{sk:k3}.
Claramente,
s3s4s1
como no caso SAT. Nos tambem temos
sksk,
e a redução de variável dupla na pergunta mostra
sk2sk.
Agora, se aplicarmos a construção acima com tamanho de bloco constante b, nós obtemos
sksbk+registro(b+1)b,
conseqüentemente
s=s.
Em particular, SETH é equivalente a s=1, e ETH é equivalente a sk>0 0 para todos k3.
Emil Jeřábek apoia Monica
fonte
Obrigado pela sua resposta! Estou curioso para saber se é possível fazerΦ e Ψprofundidade constante nesta construção? Ou seja, não sei se as fórmulas booleanas monótonas de profundidade constante de tamanho subexponencial (ou mesmo circuitos não monótonos) são conhecidas porTkn(em particular para a maioria)? Claro que há uma2nΩ(1/d) limite inferior para profundidaded, mas digamos 2n tamanho seria bom.
Sasha Kozachinskiy
Tkne, em geral, qualquer coisa computável por fórmulas de tamanho polinomial (ou seja, em NC ^ 1), possui profundidaded circuitos de tamanho 2nO(1/d). Consulte, por exemplo, cstheory.stackexchange.com/q/14700 . Vou ter que pensar se você pode torná-los monótonos, mas parece plausível.
Emil Jeřábek apoia Monica
ESTÁ BEM. Primeiro, a construção genérica funciona bem na configuração monótona: se uma função tiver fórmulas monótonas de tamanho poli, ela terá profundidaded circuitos monótonos de tamanho 2nO(1/d)poeuy(n) para qualquer d2. Segundo, paraTkn especificamente, é fácil construir profundidade monótona3 circuitos de tamanho 2O(nregistron) dividindo a entrada em blocos de tamanho Θ(nregistron).
Emil Jeřábek apoia Monica
Na verdade, empurrando um pouco mais essa idéia, ela fornece uma resposta para a pergunta original: assumindo SETH, o limite inferior já é válido para Φ CNF monótono e ΨDNF monótono. Escreverei depois.
Emil Jeřábek apoia Monica
Eu acho que você pode dividir todas as variáveis ​​em cerca de n blocos x1,...xn e depois escreva Tk1n(x1)...Tknn(xn)ϕ para cada k1+...+knn. Você pode usar2nCNF de tamanho para todas as funções de limite. Mas, no lado direito, você não terá DNF, mas uma fórmula de profundidade 3 ...
Sasha Kozachinskiy