P = NP
The present paper proves that P=NP. The proof, presented in this paper, is a constructive one: The program of a polynomial time deterministic multi-tape Turing machine M〈∃AcceptingPath〉, which determines if there exists an accepting computation path of a polynomial time non-deterministic single-tape Turing machine M〈NP 〉, is constructed explicitly (machine M〈∃AcceptingPath〉 is different for each machine M〈NP 〉). The features of machine M〈∃AcceptingPath〉 are as follows: 1) the input of machine M〈∃AcceptingPath〉 does not contain any encoded program of machine M〈NP 〉, but the program of machine M〈∃AcceptingPath〉 contains implicitly the program of machine M〈NP 〉; 2) machine M〈∃AcceptingPath〉 is based on reduction L ≤m LP (Linear Programming) instead of reductions L ≤m 3-CNF-SAT ≤ P m ILP (Integer Linear Programming) which are commonly used, wherein language L ∈NP, machine M〈NP 〉 decides L, and ≤m is polynomial time many-one reduction; reduction L ≤m 3-CNF-SAT is not used in the present paper; 3) the reduction to problem LP is a set of reductions L ≤m TCPE ≤ P m LP in fact wherein TCPE (Tape-Consistent Path Existence Problem) is a NP-complete problem defined in the present paper; 4) problem TCPE is reducible to a similar problem TCPE〈1〉 that is a special case of problems mixed-DHORN-SAT (dual Horn) and linear-CNF-SAT; problem TCPE〈1〉 is polynomial time reducible to problem ILP; unlike problem TCPE〈1〉, a polynomial time algorithm is constructed for problem TCPE in the present paper; 5) to determine if there exists an accepting computation path, it is sufficient to find a fractional solution of the resulting linear program; 6) the set of the accepting computation paths of machine M〈NP 〉 is considered as a subset of a more general set of all the computation paths in the acyclic control flow graph of polynomial size of a deterministic computer program that writes values to the tape cells and reads values from the tape cells; 7) reduction L ≤m TCPE is based on the results of reaching definitions analysis for the deterministic computer program and on the notion of network flow; 8) the resulting linear program does not express any combinatorial optimization problem polytope (like TSP polytope); 9) both to accept and reject the input of machine M〈NP 〉, polynomial t(n), an upper bound of the time complexity of machineM〈NP 〉, is not used in the program of machineM〈∃AcceptingPath〉; 10) machine M〈∃AcceptingPath〉 is a pure mathematical construction; the proof presented in the paper is not based on physics theories (but it seems it should relate to them in some a way). SergeyV.Yakhontov: Ph.D. in Theoretical Computer Science, Dept. of Computer Science, Faculty of Mathematics and Mechanics, Saint Petersburg State University, Saint Petersburg, Russian Federation; e-mail: SergeyV.Yakhontov@gmail.com, S.Yakhontov@spbu.ru; phone: +7-911-966-84-30; personal Web page: https://sites.google.com/site/sergeyvyakhontov/; current status of the paper: https://sites.google.com/site/sergeyvyakhontov/home/peqnp-paper-status/; 23-Jan-2017