wil*_*007 3 algorithm math logic discrete-mathematics
将任何命题公式转换为CNF格式的复杂性是多少？这是NP完全问题吗？
将一般Well-Formed公式转换为等效 CNF 的标准算法具有指数运行时间,因为在最坏的情况下,n子句WFF等效于2 ^ n子句CNF.
但是,您可以在多项式时间内将任意布尔公式转换为非严格等效的CNF ,但只有在布尔公式可满足时才可以满足.这是用于证明3CNF是NP完全的标准还原,使得更一般的SAT是NP完全的.看到这里.