algorithm - 将任何命题公式转换为 CNF 格式的复杂性

Question

将任何命题公式转换为 CNF 格式的复杂性是多少？这是一个NP完全问题吗？

Answer 1

将一般格式良好的公式转换为等效CNF 的标准算法具有指数运行时间，因为在最坏的情况下，n 子句 WFF 等效于 2^n 子句 CNF。

但是，您可以在多项式时间内将任意布尔公式转换为不严格等价的 CNF，但仅当布尔公式可满足时才可满足。这是用于证明 3CNF 是 NP 完全的标准归约，假设更一般的 SAT 是 NP 完全的。见这里。