为何无法通过转换为CNF在多项式时间内判定可满足性？

你的推理逻辑链本身没有矛盾，核心问题是你误解了CNF可满足性问题的复杂度属性：CNF-SAT（合取范式的可满足性判定）本身就是NP完全问题，它和通用的SAT问题是多项式时间等价的。

具体拆解关键点：

• Tseitin转换的性质是对的：它能在线性时间内将任意命题公式转换成与原公式**可满足性等价（SAT等价）**的CNF，引入新变量确实不影响“是否存在赋值使公式为真”这个核心判定目标，这一步没有问题。
• 你假设“CNF的可满足性可在多项式时间内判定”，这个假设本身就等价于P=NP——因为CNF-SAT是NP完全问题的典型代表，所有NP问题都能多项式归约到它。如果这个假设成立，那所有SAT问题（包括非CNF的）自然都能多项式解决，这是一个合理的推导，并不存在矛盾，只是这个假设目前既未被证明也未被证伪。
• 你觉得有矛盾，本质是误以为“CNF形式的公式可满足性判定比通用SAT简单”，但实际上CNF-SAT就是SAT问题的核心子集，它的NP完全性正是SAT问题NP完全性的基础——通用SAT问题能多项式归约到CNF-SAT，反之亦然。

内容的提问来源于stack exchange，提问作者RunTimeError31415