The Mathematics of P vs NP by hemant pandey - HTML preview

156

157

158

159

160

161

162

163

The present proof attempts to resolve P=NP by the proposed solution of NP complete Hamiltonians path problem or Euclidean Traveling Salesman Problem, in 2-D, in polynomial time. The proof is using topology, geometry and properties of convex polygons. The proof assumes Euclidean TSP in 2-D case and hence the triangle inequality is to be satisfied.

We have attempted to find an optimal tour for Euclidean travelling salesman problem, by using methods described in the paper in polynomial time of order five i.e. O (5).

164

165

166

167

168

169

Key   words:        Polynomial   time   problem,   Non-deterministic   Polynomial   time   problem, Hamiltonians path problem, Euclidean Traveling salesman’s problem, NP-Complete problem.

MEANING OF SYMBOLS

P             -              Polynomial time problem

170

NP          -              Non-deterministic polynomial time problem

171

=             -              is equal to

172

n          -              Pi (180 in trigonometry)

173

#             -              Is not equal to

174

nK                  -              ‘n’ rose to power ‘K’

175

n!            -              n factorial

176

C(n,k) -           Combination of ‘n’ things taken ‘K’ at a time.

177

I              -              Set of Integers.

178

HPP       -              Hamiltonians path problem

179

TSP        -              Traveling Salesman Problem

180

181

182

ETSP -          Euclidean Traveling Salesman Problem

c      -            This implies that