Os solucionadores SMT como Z3 ou Boolector usam um conjunto complexo de heurísticas para resolver problemas. No entanto, isso também dificulta muito a previsão do desempenho de um solucionador para um determinado problema. Minha pergunta é assim: Questão Existe uma maneira de entender ou obter...
Gostaria de saber onde posso recorrer para uma introdução boa e gentil ao k-SAT (isso pode ser para matemáticos que podem não ter uma boa formação em ciência da computação). Também gostaria de conhecer trabalhos que talvez pesquisem ou expliquem os métodos atuais usados para resolver o k-SAT....
O problema padrão 1-em-3 SAT (ou XSAT ou X3SAT) é: Instância : uma fórmula CNF com todas as cláusulas contendo exatamente 3 literais. Pergunta : existe uma atribuição satisfatória configurando exatamente 1 literal por cláusula? O problema é NP-completo e permanece difícil, mesmo se nenhuma...
Gostaria de saber se existem abordagens que formulam um problema de roteamento de veículo com Windows de tempo ( VRPTW ) (como um problema de decisão) como uma instância de SAT / SMT? (alternativa: TSP) Por exemplo: "Existe uma solução válida para visitar todos os clientes dentro de suas janelas...
Considere o problema clássico # P-complete # 3SAT, ou seja, contar o número de avaliações para tornar um 3CNF com variáveis satisfatórias. Estou interessado na aproximação aditiva . Claramente, existe um algoritmo trivial para atingir o erro 2 n - 1 , mas se k < 2 n - 1 , é possível ter um...
Considere uma fórmula Monotone 3CNF com as duas restrições adicionais a seguir: Cada variável aparece em exatamente cláusulas.222 Dadas cláusulas, elas compartilham no máximo variável.222111 Eu gostaria de saber o quão difícil é contar as tarefas satisfatórias dessa fórmula. Atualização...
É possível encontrar uma redução na contagem de #SAT para #HornSAT? Eu não encontrei esta pergunta postada aqui, então decidi verificar se alguém tem alguma resposta para isso. Deixe-me explicar o que quero dizer com contagem de redução. Suponha que são dois problemas de contagem. Por exemplo,...
O problema # MONOTONE-2SAT é conhecido por # P-complete. Isso significa que #SAT pode ser reduzido a ele. Minha pergunta é: dada uma instância #SAT , que é a transformação que converte F na instância correspondente # MONOTONE-2SAT F ′ ?FFFFFFF′F′F' A segunda questão é: deixar ser o número de...
No artigo "Codificação eficiente de CNF para selecionar 1 de N objetos", os autores apresentam sua técnica de "variável de comando" para codificar a restrição e depois falam sobre o problema do buraco de pombo. Como meu erro pode existir no entendimento de nível inferior, deixe-me declarar o que...
Em poucas palavras, minha pergunta é: a prova original de Karp está reduzindo o SAT para 3SAT desnecessariamente elaborado? Os detalhes são os seguintes. Em seu artigo de 1972, Redutibilidade entre problemas combinatórios , Karp provou que o SAT se reduz a 3SAT, afirmando: Substituir um...
O problema de satisfação máxima (Max-Sat) é o problema de encontrar o número máximo de cláusulas que podem ser satisfeitas em uma instância de satisfação booleana. O problema exatamente 1 em 2 Sat pergunta, dado um conjunto de cláusulas, cada uma com dois literais, existe um conjunto de literais,...
Vamos definir o problema SAT : Dado F 3 , uma fórmula 3-CNF satisfatória e F 2 , uma fórmula 2-CNF ( F 3 e F 2 são definidos nas mesmas variáveis). É F 3 ∧ F 2 satisfiable?(3,2)s(3,2)s(3,2)_sF3F3F_3F2F2F_2F3F3F_3F2F2F_2F3∧F2F3∧F2F_3 \wedge F_2 Qual é a complexidade desse problema? (Já foi estudado...
Tentar encontrar a solução ideal para o WEIGHTED-MAX-3SAT, a versão ponderada do problema de otimização do 3-SAT, é difícil para o NP. De fato, mesmo aproximando-se arbitrariamente da versão não ponderada do MAX-SAT é comprovadamente difícil o NP pelo Teorema do PCP. Um algoritmo canônico para...
De acordo com o XOR Satisfiability Solver Module para integração de DPLL por Tero Laitinen, precisamos de cláusulas n - 1 CNF para converter uma cláusula XOR-SAT n literal se não quisermos aumentar o número de literais. Portanto, entendo que o custo computacional para converter uma expressão...
(Publiquei esta pergunta no CS há dez dias, sem resposta desde então - então publico aqui.) Qualquer fórmula CNF pode ser transformada em tempo polinomial em uma fórmula 3-CNF usando novas variáveis. Nem sempre é possível se novas variáveis não são permitidas (por exemplo, a fórmula de cláusula...