将任何命题公式转换为CNF格式的复杂性是什么？这是一个NP完全问题吗？
最佳答案
自in the worst case a n-clauses WFF is equivalento to a 2^n-clauses CNF以来，将一般格式良好的公式转换为等效的 CNF的标准算法具有指数运行时间。
但是，您可以在多项式时间内将任意 bool 公式转换为不是严格等价的CNF，但是仅当 bool 公式满足时才可以满足。鉴于更一般的SAT是NP完整的，这是用来证明3CNF是NP完整的标准简化。参见here。
关于algorithm - 将任何命题公式转换为CNF格式的复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11579963/