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

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

·         2.      NP-    NP means type of problems which are solvable in polynomial time by a non- deterministic Turing machine only. Symbol NP stands for ‘Non-deterministic Polynomial’.

·         3.    NP-Hard - A problem is said to be NP-Hard if an algorithm for solving it could be transformed to solving any other NP problem.

·         4.    NP- Complete- A problem which is both NP and NP-Hard is called NP complete problem.

·         5.     Triangle Inequality- According to the triangle inequality sum of two sides of a triangle is greater than the third side. In almost all cases of Euclidean TSP the triangle is satisfied.

·         6.    Local optimal tour: A tour may be termed as a local optimal tour if it is the optimal tour w.r.t. to the points existing on the network. This tour may or may not be the optimal tour.

·         7. Optimal branch: The optimal branch may be defined as the nearest branch chosen according to the lowest sum rule or ‘a+b-c rule.’

205

·         8.a+b-c rule: Refer page 12

206

207

208

·         9. Interior local improvements: Local improvements are said to be interior local improvements if we change only the relative positions of points without constructing a virtual segment.

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

·        10. Exterior local improvements: If we change position of points by creating a virtual segment we get a external local improvement. Note that once this improvement is introduced we cannot return to our starting point by simply reversing the steps as reversal of a virtual segment is not defined as it is arbitrary.