Research

This paper analyzes the use of diagonalization as applied by Georg Cantor and Alan Turing and shows how their claims do not logically follow from their respective proofs. In Cantor's work, diagonalization and contradiction are used to prove the set of infinite binary sequences does “not have the power of the number-sequence 1, 2, 3, ..., v, ...” i.e., the set is not enumerable. In Turing's work, the diagonal process and contradiction are used to prove the computable sequences are not enumerable. Both proofs incorrectly use contradiction, due to the fact that they assume the truth of two statements and recognize only one. Namely, they assume (1) the set in question is enumerable and (2) the proposed sequence is possible. It is seen that neither proof can concretely and definitively disprove the first assumption as they heavily rely on the second assumption.

It is shown that any two clauses in an instance of 3SAT sharing the same terminal which is positive in one clause and negated in the other can imply a new clause composed of the remaining terms from both clauses. Clauses can also imply other clauses as long as all the terms in the implying clauses exist in the implied clause. It is shown an instance of 3SAT is unsatisfiable if and only if it can derive contradicting 1-terminal clauses in exponential time. It is further shown that these contradicting clauses can be implied with the aforementioned techniques without processing clauses of length 4 or greater, reducing the computation to polynomial time. Therefore there is a polynomial time algorithm that will produce contradicting 1-terminal clauses if and only if the instance of 3SAT is unsatisfiable. Since such an algorithm exists and 3SAT is NP-Complete, we can conclude P = NP.

A visual explanation of the polynomial time algorithm for 3SAT.