A Simple Elementary Proof of P=NP based on the Relational Model of E. F. Codd
share
The P versus NP problem is studied under the relational model of E. F. Codd. To simplify the problem, a periodic machine is coined as a nondeterministic Turing machine, which only changes its tape head direction at the tape ends. A time T(n) decider nondeterministic Turing machine is reduced to a time O(T(n)*T(n)) periodic machine. For a periodic machine in polynomial time p(n), on an input of length n, its up to exponential number of valid sequences of choices are normalized into a relational model of O(p(n)) shared trichoices. By enumerating all the O(p(n)) shared trichoices, proved by mathematical induction, the periodic machine is simulated in time O(p(n)*p(n)*p(n)*logn) under logarithmic cost criterion by a simple computer program. A simple elementary proof of P=NP is obtained.
READ FULL TEXT