In this paper we have to demonstrate that if we claim to have an algorithm that solves CSAT in polynomial time with a DTM (Deterministic Turing Machine), then we have to admit that: there is a counterexample that invalidates the correctness of the algorithm. This is because if we suppose that it can prove that an elenkhos formula (a formula that lists the negated codes of all models) is a contradiction, and if we change exactly a specific boolean variable of that formula, then we have proven that: in this case the algorithm will always fail.
翻译:在这份文件中,我们必须证明,如果我们声称有一个算法,用DTM(确定性图灵机)在多元时间用DTM(确定性图灵机)解决了CSAT,那么我们就必须承认:有一个反比的例子使算法的正确性失效。 这是因为如果我们假设它能够证明埃伦霍斯公式(列出所有模型的否定代码的公式)是矛盾的,如果我们完全改变了该公式的具体布林变量,那么我们就证明了:在这种情况下,算法将永远失败。