Perguntas com a marcação «formulas»

18
Fórmula CNF equivalente mais curta

Seja uma fórmula CNF satisfatória com variáveis ​​e cláusulas . Seja o espaço de solução de .F1F1F_1m S F 1 F 1nnnmmmSF1SF1S_{F_1}F1F1F_1 Considere o problema de determinar, dada a , outra Fórmula CNF com o mesmo conjunto de variáveis ​​que , com (o mesmo espaço de solução que ), mas com o mínimo...

18
É possível testar se um número computável é racional ou inteiro?

É possível testar algoritmicamente se um número computável é racional ou inteiro? Em outras palavras, seria possível para uma biblioteca que implementa números computáveis ​​fornecer as funções isIntegerou isRational? Suponho que isso não seja possível e que isso esteja de alguma forma relacionado...

8
Conversão entre k-SAT e XOR-SAT

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...