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 pore 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.
Portanto, existe um intervalo entre e time. Minha pergunta é se é conhecido algum algoritmo melhor ou melhor redução do SETH?
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 )
fonte