Hemant Pandey from India Solves P vs. NP
in [Logic]
|
Prev: O-PA, CON(ZF) and non-standard models of ZF.
Next: Towards avoiding paradoxes with set theory: Corrected.
From: flowbase on 31 Oct 2009 13:15 Page 0 of 26 1 2 3 4 5 6 7 8 9 Title Page 10 1. Contents 11 2. Author s Profile 12 3. Cover Letter 13 4. Abstract 14 5. Manuscript 15 6. References 16 17 18 19 20 21 22 23 24 25 26 27 28 29 Page 1 of 26 30 31 Contents 32 33 34 Title Page 0 35 Table of Contents ...1 36 Authors profile 2 37 Cover letter 3 38 Abstract and title 4 39 Meaning of symbols and definition ... 5 40 Introduction.............................................................................................................................................................. 6 41 1.1 The complexity class of P and NP............................................................................................................. 6 42 1.2 The concept of NP completeness ............................................................................................................. 7 43 2. The Problem......................................................................................................................................................... 7 44 2.1 Meaning and definition of P & NP: .......................................................................................................... 8 45 2.2 Proposed Result ............................................................................................................................................. 9 46 3.Proposed Proof .. ................................................................ 9 47 3.1 The issue of shortest route-Special case ......10 48 3.2 Theorem ... 10 49 4.The issue of shortest route or the optimal tour-General case .... 11 50 4.1The General Domain . ..12 51 4.2 The Next network case . .15 52 4.3 The Case of hypothetical diagonals/Virtual Segments . . 16 53 4.4 The Segment Connection ..17 54 5. The last check .17 55 6. The Proof of the route being the shortest 18 56 6.1 Properties of the shortest route . 18 57 7. Final concerns about the optimal tour.........................................................19 58 8.One step check for the optimal tour ..20 59 9. Few comparisons with standard known heuristics . 20 60 10. Algorithm/ heuristics for finding the shortest route . .. 21 61 11. Mathematical Equivalence . .22 62 12. Few comparisons with actual solution . a deeper insight ... 23 63 13. Further progress and consequences . ..24 64 Final call for the reader ..24 65 Page 2 of 26 66 67 68 69 70 Authors Profile 71 72 73 74 Author: Hemant Pandey 75 Affiliation: Presently working as lecturer for IIT JEE training institute TIME. 76 Worked for City Montessary School (CMS) Innovation Wing (IW),Amelox college tutor 77 www.amelox.com 78 Job Profile: Content Developer; Writer 79 Branch: Main Branch, 80 Station Road, Lucknow 81 Writing profile: Currently working on a text book for 82 Grade 11-12 of mathematics with Amelox College Tutor; California (USA) 83 Qualification: Masters of Science in Mathematics and currently a Researcher 84 85 86 Postal Address: 87 88 16/732, Indira Nagar,Lucknow. 89 Uttar Pradesh 226016(Pin) India 90 Mobile Number +91-9336291008, +91-9338202560 91 92 93 Mailing Address: 94 95 E-mail- ajay_fermat(a)rediffmail.com 96 E-mail- ajay_euler(a)rediffmail.com 97 E-mail- ajay_gauss(a)rediffmail.com Page 3 of 26 98 99 100 101 102 103 104 105 106 107 Cover Letter 108 109 Dear Sir, 110 My name is hemant pandey and I am a young researcher. 111 I am proposing an paper on P Vs NP problem for possible publication. The main 112 argument used in the paper is to search an optimal tour for traveling salesmans 113 problem in Euclidean geometry in 2-D, in polynomial time. 114 This is to certify that the work is original and has not been submitted any where else for 115 publication consideration. 116 Details are in the pdf attachment. 117 118 Sincerely, 119 Hemant Pandey 120 121 122 123 124 125 126 127 Page 4 of 26 128 129 130 131 132 133 134 135 136 137 2ND JULY 2007 138 139 THE MATHEMATICS OF P V NP 140 141 142 143 144 THE ABSTRACT 145 P Vs NP problem is an open problem in the theory of optimization and asks whether two of 146 the important complexity classes, P and NP are same. 147 The P Vs NP problem directly affects one of the most basic things of our modern day survival, 148 the Internet security. This classic problem in theoretical computer science was formulated by 149 Stephen Cook in 1971. 150 The RSA ciphering-deciphering technology or public key cryptography has seeds of its 151 success, in assumption of the fact that P is not equal to NP. If we assume truth of this papers 152 result then newer methods have to be searched for coding public keys, and that is surely an 153 interesting task as if now we have supposed to reach a stagnation point. 154 The mathematical gain of supposed truth of this result is that it opens a search for solution of 155 the 3000 plus NP complete problems and much more. Page 5 of 26 The present proof attempts to resolve P=NP by the proposed solution 156 of NP complete 157 Hamiltonians path problem or Euclidean Traveling Salesman Problem, in 2-D, in polynomial 158 time. The proof is using topology, geometry and properties of convex polygons. The proof 159 assumes Euclidean TSP in 2-D case and hence the triangle inequality is to be satisfied. 160 We have attempted to find an optimal tour for Euclidean travelling salesman problem, by 161 using methods described in the paper in polynomial time of order five i.e. O (5). 162 163 164 Key words: Polynomial time problem, Non-deterministic Polynomial time problem, 165 Hamiltonians path problem, Euclidean Traveling salesmans problem, NP-Complete problem. 166 167 168 MEANING OF SYMBOLS 169 P - Polynomial time problem 170 NP - Non-deterministic polynomial time problem 171 = - is equal to 172 . - 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 ETSP - Euclidean Traveling Salesman Problem 181 . - This implies that 182 . - Therefore 183 DEFINITIONS 184 185 . 1. P - P means problems whose solution is bounded by a polynomial i.e. whose 186 solution requires size of inputs expressible as a polynomial of the form ,where n 187 are number of inputs, k is an integer and C is an arbitrary constant. Such problems 188 are said to be of order n .Symbol P stands for Polynomial. Page 6 of 26 .. 2. NP- NP means type of problems which are solvable 189 in polynomial time by a 190 non- deterministic Turing machine only. Symbol NP stands for Non- deterministic 191 Polynomial. 192 . 3. NP-Hard - A problem is said to be NP-Hard if an algorithm for solving it could be 193 transformed to solving any other NP problem. 194 195 . 4. NP- Complete- A problem which is both NP and NP-Hard is called NP complete 196 problem. 197 . 5. Triangle Inequality- According to the triangle inequality sum of two sides of a 198 triangle is greater than the third side. In almost all cases of Euclidean TSP the 199 triangle is satisfied. 200 . 6. Local optimal tour: A tour may be termed as a local optimal tour if it is the 201 optimal tour w.r.t. to the points existing on the network. This tour may or may not 202 be the optimal tour. 203 . 7. Optimal branch: The optimal branch may be defined as the nearest branch chosen 204 according to the lowest sum rule or a+b-c rule. 205 . 8.a+b-c rule: Refer page 12 206 . 9. Interior local improvements: Local improvements are said to be interior local 207 improvements if we change only the relative positions of points without 208 constructing a virtual segment. 209 . 10. Exterior local improvements: If we change position of points by creating a 210 virtual segment we get a external local improvement. Note that once this 211 improvement is introduced we cannot return to our starting point by simply 212 reversing the steps as reversal of a virtual segment is not defined as it is arbitrary. 213 214 215 216 217 218 1. INTRODUCTION 219 Computation complexity had its seeds sown way back in 1936 when Turing developed his 220 theoretical computational model. Further developments resulted in 1960s by Hartmanis and 221 Stearns when they coined the idea to measure time and space as a function of the length of the 222 input. 223 Page 7 of 26 The work of Cook and Karp in early 70s gave birth to the most important 224 and fundamental 225 concept of computational complexity, NP-Completeness and its most fundamental question, 226 whether P= NP. 227 228 1.1. THE COMPLEXITY CLASS OF P AND NP 229 The relationship between the complexity class P and NP is an unsolved question in theoretical 230 computer science. 231 The relationship between the complexity classes P and NP is studied in computational 232 complexity theory which deals with the resources required to solve a given problem. The 233 resources may be the steps required to solve a problem and space needed for formulation of a 234 solution. 235 The computational machine in the context is assumed to be deterministic, i.e. it always performs 236 sequential operations, one after another. 237 Theoretically P class consists of problems that can be solved on a deterministic computational 238 machine in amount of time which assumes polynomial equations in the size of inputs. 239 Mathematically this is measured as order of a problem. For P class this is represented as O (K), 240 where K is a positive integer .We are attempting a solution of order five i.e. O (5). 241 On the other hand NP class means problems whose solution can only be verified on a 242 deterministic computational machine and can be found only by a Non- deterministic 243 computational machine in polynomial time. 244 245 1.2. THE CONCEPT OF NP COMPLETENESS 246 NP complete problems are those problems which are the tough most and hardest problems in 247 NP.NP complete problems are those NP- hard problems which are in NP. 248 Precisely a NP-hard problem is one into which any NP problem can be transformed in 249 polynomial time. 250 The beginning of NP- complete problems attributes to the Boolean satisfiability problem, which 251 was proved to be NP complete by Stephen Cook in early 70s.This is now also known as Cooks 252 theorem. The common NP complete problems are subset sum problem, minesweeper, Traveling 253 salesmans problem and Hamiltonians path problem. 254 255 256 257 258 Page 8 of 26 259 2. THE PROBLEM 260 261 Statement: 262 The P Vs NP problem has a classic one line statement whether P=NP? 263 Mathematically P Vs NP states 264 P = NP or P # NP i.e. whether or not P is equal to NP. 265 2.1 MEANING AND DEFINITION OF P & NP: - 266 P states for polynomial time problems, problems that can be effectively solved in polynomial 267 time by using a deterministic computer. Polynomial time means reasonable time in common 268 terms and in technical terms it means that it is expressible in the form of a polynomial equation. 269 .P problems are characterized by a polynomial equation. 270 i.e. P =CnK where n is the size of inputs or data and K is a positive integer. We call that these are 271 of order K, i.e., O (K). 272 Precisely 273 P = Polynomial time i.e. time required to solve a P type problem. 274 C = Arbitrary constant. 275 n =Size of input or data. 276 K =Order of P type problem. 277 Hence P represents a class of polynomial in which total numbers of outcomes are proportional 278 to an integral power of inputs. 279 NP problems are those in which time required to get a solution is unreasonably large, though 280 the cases are too much, to calculate each case itself may need trivial arithmetic only. 281 Only problem is number of cases, which are too large for a normal computer to handle fully in 282 polynomial time. 283 NP literally means non- deterministic polynomial time problem i.e. the problem which can be 284 solved in polynomial time only by a non deterministic computational machine only. 285 A computer in polynomial or reasonable time cannot handle NP problem. 286 More often than not there are NP problems that may take centuries for a full solution by brute287 force method i.e. by method of checking all options. 288 There are about 3000 plus NP complete problems. 289 A NP complete problem is one that is father of all NP problems. It means that if one NP 290 complete problem is solvable in polynomial time so can be any other problem. Page 9 of 26 Mathematically NP completeness is the generalization of NP problems. 291 In order to prove or 292 disprove P = NP, we have to prove or disprove it for one of those 3000 NP complete general, 293 problems. 294 2.2 RESULT: 295 We propose a new result P =NP; We will establish this result for NP complete Hamiltonians 296 path problem, or Euclidean Traveling salesmans problem. We will find an optimal tour for 297 ETSP with the help of geometrical and topological properties of polygons. 298 Our proof aims to solve Hamiltonians path problem or Euclidean Traveling salesmans problem 299 in polynomial time of fifth degree at most. 300 i.e. for HPP or TSP 301 We propose P =Cn5 at most, i.e. NP complete ETSP can be effectively solved in polynomial time of 302 order 5. 303 3. THE PROOF 304 Hamiltonians path problem HPP or Traveling salesman problem TSP is a well known NP 305 complete problem. We would try to establish that it is solvable in polynomial time of fifth degree 306 at most. Before that we must state TSP or HPP. 307 ETSP: Suppose there is a salesperson that has to visit several cities in order to sell business. He 308 has the specified map of all the cities that come in his way. Obviously his problem is to find 309 shortest possible route or the optimal tour that covers all the cities. We assume Euclidean TSP 310 onwards so triangle inequality is satisfied and all the maps are drawn on a 2-D plane. 311 Obviously we can name all the routes and get the answer instantaneously. But the bone in the 312 dish is not summing the distances from city to city. It is the number of such cases. 313 For n cities total cases turn out to be n! , which is a whopping number even for values of n as 314 small as 100. 315 Therefore even for modest 100-city tour there are 100! cases. 316 These cases are too large for a deterministic computer to handle. It may take decades for a 317 fastest computer on earth to find optimal tour or shortest possible route for say 1000 cities only. 318 Actually computers can handle polynomial time processes i.e. where P =Cnk. 319 These Polynomials doesnt grow that fast if n is the variable or size of data. 320 Here n = Number of cities or size of data or input. 321 P =Cn10 (say) 322 Doesnt grows as fast as say P =C.3n 323 Here latter are called exponential time processes. After them comes NP processes. 324 Now we will prove that HPP or ETSP is solvable in polynomial time using geometrical & 325 topological properties of polygons applied on topologically equivalent maps. Page 10 of 26 Mathematically we will show that total cases for ETSP are reducible to 326 Cn^5 from n!, which 327 means that the solution becomes polynomial. 328 Our solution is geometrical in nature and assumes ETSP on topologically equivalent maps. 329 For a start we assume that maps available are topologically correct i.e. in which relative 330 distances matter and no scaling is required. The emphasis is on the property exhibited by each 331 point and its relative position. 332 For e.g. in Fig 1 below 333 d(A1A2) < d (A1A3 ) < d (A1A4 ) etc. 334 Here d(Ai Aj ) is usual distance function measuring distance between any arbitrary points Ai 335 and Aj relative to distance between other arbitrary points Am and An (say). 336 337 Space for Fig.1 338 339 340 341 342 343 344 345 346 347 348 349 350 These maps are topological maps only. We again state that the distances are relative only and 351 emphasis is on the property exhibited by each point not on their actual position. 352 353 354 355 356 357 3.1 THE ISSUE OF SHORTEST ROUTE-SPECIAL CASE 358 POINTS ON THE PERIPHERY OF CONVEX POLYGON Page 11 of 26 359 360 We will state and prove a general theorem about shortest route through 361 the periphery of a 362 standard convex polygon.. We start with few definitions. 363 364 Standard convex Polygon: A standard convex polygon or SCP for short is one in which all the 365 internal angles are between 900and 1800. A peculiar property of SCP is that all diagonals are 366 greater than the two sides forming it, or adjacent sides to it. It is easy to establish since in a 367 right triangle hypotenuse is diagonal or greatest side and as the opposite angle grows the 368 diagonal side dilates. So if one angle is larger than 900 then one side i.e. side opposite to the 369 before said angle is the largest side. 370 Now we are in a position to state our former result. 371 3.2 THEOREM 372 For all points lying on the periphery of a SCP, the shortest route between them is through 373 the peripheral path. 374 This can be established without any trouble. Any other route other than peripheral route will 375 include one or more diagonals. As stated before in SCP the diagonals are larger than the 376 forming sides. Hence if three diagonals replace three sides they would increase the net distance. 377 We can prove it rigorously too as follows: - 378 379 380 381 Space for Fig. 2 382 383 384 385 386 387 388 389 390 391 392 393 Let the original route value along periphery be N Page 12 of 26 Case 1: When a diagonal is joined between two 394 consecutive points 395 Let A14 is joined to A12, so the point A13 is now out of network. [Refer Fig.2]. 396 Now since we have to cover each point of the network, A13 has to be joined to some other 397 point. Let A13 is joined to A3 and A4.These points are arbitrary .The important point is not the 398 point but the property exhibited by each point. If A13 is joined to any other point the property 399 exhibited by the point would be the same as with this point. Note we are talking of topological 400 properties where only the relative position matters. 401 402.Now new network distance is 403 N-A14A13-A13A12+A14A12+A3A13A4A13-A3A4 404 Now A14A12 >A14A13 (A14A12 is the adjacent diagonal of SCP and by the definition of SCP it 405 is greater than the side forming it) 406 Further A3A13 >A13A12 (Since by the definition of SCP the shortest distance from a point on the 407 periphery is next point to it on either side, all other branches from emerging from it are the 408 diagonals) 409 Finally A4A13>A3A4 (A4A13 is the adjacent diagonal of SCP and by the definition of SCP it is 410 greater than the side forming it) 411 412.The Net network distance increases as sum of the adding distances is greater than the 413 subtracting distances. 414 Hence for the points laying on a standard polygon the shortest route or the optimal tour is 415 along the periphery. 416 417 Case 2: When a diagonal is joined between any two non consecutive points 418 We now consider the case when a diagonal is joined between non consecutive points. The proof 419 is similar. Let us take any arbitrary point .Let a diagonal be joined between A5A10.So points 420 from A6 to A9 are abundant. Let these points be joined to segment A1A15. 421 Now adding distance =A5A10 +A1A6+A9A15 422 And subtracting distance=A5A6+A9A10+A1A15 423 Now A5A10 > A5A6 (A5A10 is the adjacent diagonal to A5A6 and by definition of SCP 424 former is greater than the latter) 425 A1A6 > A1A15 (Same reason as above) 426 & A9A15 > A9A10 (Same reason as above) 427 As stated before this proof is general since the relative position of points and property exhibited 428 by the point matters. 429 430 431 Page 13 of 26 432 IMPORTANT: Although this theorem is a new result but the proof works very 433 well without the 434 assumptions of the proof. This proof may save few steps but it does in no way affect the truth of 435 the result (given in next section) or the order of given problem. This is provided only as a 436 guideline for the shortest route if the points lie on the periphery of a SCP. 437 438 6. THE ISSUE OF SHORTEST ROUTE OR THE OPTIMAL TOUR-GENERAL 439 4.THE ISSUE OF SHORTEST ROUTE OR THE 440 OPTIMAL TOUR-GENERAL CASE 441 442 4.1 THE GENERAL DOMAIN 443 How can we use the before proved theorem or otherwise, to get the shortest route or the 444 optimal tour between the points? 445 Here is a possible answer. 446 447 448 449 . . 450 . . . . . . . . . . 451 . . . . . . 452 . . . . . . . . . 453 . . . . 454 . . . . . . . . . 455 . . . . . . 456 . . . . . . . . 457 .. . .. . . . . 458 . 459 . . . . . . . 460 . . . 461 Page 14 of 26 462 463 464 Consider the general domain of points shown above. The orientation 465 of the points is 466 arbitrary. The important point is not the points or their placement but the property 467 exhibited by each point and its relative position. Our basic approach for the shortest 468 route is that we start from the shortest and keep it shortest all the while. With the help 469 of this approach we will get a shorter tour which is at least locally optimal, i.e. optimal 470 w.r.t. to the starting points. After that we apply corrections or arrays of corrections to 471 get the optimal (Universal) tour. Even if the previous result is not used in general we 472 start from any route and with the process of constantly improving our route and 473 discarding longer routes in the process we reach at the shortest route. The method used 474 is basically the method of elimination of longer routes and careful selection of shorter 475 routes. 476 We start with the ouster most mesh of one map and join them so the maximum numbers 477 of destinations lie on a standard convex polygon. From theorem the shortest route lies 478 on the periphery for these cities. Even if it does not hold good then also we join them to 479 all the exterior points and proceed. 480 Our next object is to join to these branches the points which are nearest to them than 481 any other two points, branch or segment. For this we calculate a +b c for all n cities 482 for all the branches of Outer mesh if a +b c is minimum for any of the branches we 483 join it to the branch. This may be termed as nearest or cheapest insertion to the outer 484 convex shell. 485 We would like to define a + b c rule. In the Fig.[3] if point O is added to the network 486 to the segment A1A2 then 487 a = Adding distance on the segment of the network due to new point O and 488 point A1 of line segment A1A2. 489 490 b = Adding distance on the segment of the network due to new point O and 491 point A2 of line segment A1A2. 492 c = Subtracting distance on the network due to the segment A1A2. 493 494 Space for Fig.3 495 496 497 498 Page 15 of 26 499 500 501 502 503 . a +b c 504 = Net addition to the existing network due to new point O. 505 As seen above for the section A1O, A2O is the adding distances & A1A2 is the subtracting 506 distance from the network, see [Fig.3]. We find this value for all segments 507 We repeat the process for new joined branches till we reach a network that looks like 508 [Fig.4] 509 510 Space for Fig. 4 511 512 513 514 515 516 517 518 519 520 521 522 The above network has following properties. 523 This is the shortest route or the optimal tour (local optimal tour) between the points on 524 the network joined so far. No confusion about the term local optimal tour should stem 525 out. This is the optimal tour for the points joined so far w.r.t. themselves but this is a 526 local optimal tour w.r.t. the points all the points as better combination may exist 527 between these and other points in the optimal tour. We would take this case under the 528 heading virtual segments or hypothetical diagonals. The virtual segment case puts each 529 point under testimony, and each point is considered vulnerable to a change in position, 530 after application of point to segment (Section 6.1) and segment to segment rule (Section 531 6.2). Page 16 of 26 All the points that are left are either nearer to themselves or to 532 branches other than on 533 the network. These may be called hypothetical diagonals or virtual segments. The name 534 pops up as they are hypothetical diagonals or virtual segments which can still be joined 535 between the points on the already existing network of [Fig.4] 536 537 4.2 THE NEXT NETWORK CASE 538 After we have the original network intact we start with other independent points, independent 539 in the sense they are nearer to themselves than to any of the points on the existing network. We 540 repeat the same process of the general domain till all the points gets exhausted [refer to Fig. 5]. 541 542 Space for Fig. 5 543 544 545 546 547 548 549 550 551 So our net shortest route may now look like fig. 5. We have taken four networks for simplicity. 552 The four networks are respectively the shortest route between the particles of the 553 corresponding networks .We now use segment rule to join these networks. 554 It is that the networks are joined via the closest segment. 555 The segment length is calculated as follows. (For details refer section 6.4) 556 a + b c d ; Here a ,b are adding distance & c , d are subtracting distances. 557 Suppose we have to join A1A2 to B2B3 [Refer Fig. 6]. 558 The net adding distance is 559 a =A1B2 560 b =A2B3 & 561 Net subtracting distance is A1A2 & B2B3. Similarly we check for other segment B3B4 (say). 562 For whichever two segments the a +b c d is minimum we join them. 563 Next case is the case of hypothetical diagonals. Now our shortest route may look like Page 17 of 26 [Fig. 6] (For simplicity exact geometrical figures are assumed, the original 564 networks are usually 565 distorted enough) 566 The case of hypothetical diagonals will be dealt after the present case of next network. 567 568 569 570 4.3 THE CASE OF HYPOTHETICAL DIAGONALS/VIRTUAL SEGMENTS 571 572 Again we may have the shortest route between the points one more query arises. We may 573 join any two points and consider a hypothetical diagonal. Then we may join the nearest 574 points to this hypothetical diagonal and calculate the whole mesh if it comes lower than 575 previous we take this hypothetical route as a new shortest route. The process is repeated for 576 all points and we arrive at the shortest possible route between the points. 577 578 579 580 581 582 4.4 THE SEGMENT CONNECTION 583 584 The route which we got so far may be the shorter route but it may not be the shortest. The 585 route which we have got so far is no doubt the shorter route as compared to many other 586 routes but it is still possible that some changes may result in a further shorter route. 587 Let us examine what these changes could be. The route which we got till now has one 588 property that all the points are joined to the nearest branches to them, but it is still possible 589 that some segment may have been joined to a segment which may not be nearest to it .For 590 that we must do a segment to segment check via similar rule which we used for joining 591 points to the nearest branches to them. This rule may be called a + b-c-d rule. Here a and b 592 are the adding distances and c andd are the subtracting distances from the network when 593 a particular segment is joined to a new segment. So we will check all the segments so they 594 may have been joined to their respective nearest segments. So if we get any of the segments 595 not been connected to the nearest segment we join it and join the other points to their 596 second nearest segments. By the repeated application of the segment test we reach a 597 saturation point when no further correction may be done. This is the shortest route. Our 598 shortest route may look like Fig [6]. Page 18 of 26 Note this is only a guide route. The real route may look quite different from 599 this hypothetical 600 route. We must mention that their can be no general shapes for the shortest route as the 601 route changes after each correction and depending on the position of the points it may take 602 any shape. 603 We will now prove that this route is the shortest. For doing so we will start with the 604 properties of the shortest route and see that our shortest route satisfies the properties 605 mentioned. 606 5. THE LAST CHECK 607 Till now we have got a shortest route between the existing points. But to prove it is the shortest 608 route indeed we check for all points a + b c again if there is any point not joined to the nearest 609 branch it will come to our notice. 610 So the last check infect establishes that no other subsequent alterations to the position of the 611 points on the network may yield another shorter route than the existing one. 612 613 614 615 616 617 618 6. THE PROOF OF THE ROUTE BEING THE 619 SHORTEST/OPTIMAL 620 621 622 The basic question arises what are the properties of the shortest route which make it the 623 shortest. Strictly speaking there are two properties basically. Actually any shortest route (or any 624 route) consists of points and segments. These points and segments are joined to their nearest 625 possible branches. The above property makes the route the shortest. 626 6.1PROPERTIES OF THE SHORTEST ROUTE Page 19 of 26 We will start with the properties of any shortest route which may exist 627 between the points of the 628 shortest route. Any such general shortest route must exhibit two necessary and sufficient 629 properties to be called the shortest route. 630 Property 1: All the points should be joined to the nearest branch to it. 631 Property 2: Each segment must be joined to the nearest segment to it. 632 We would explain these two points in detail. For illustration only let us consider the following 633 hypothetical route of [Fig.7] supposed to be the shortest route between these points. 634 Note: The route shown is topological and hypothetical and their may be other shortest route 635 between these points. The main point is not the position of points but the property each point 636 exhibits. 637 638 Now each point on the network is joined to a branch for which a+b- c is minimum possible. If it 639 has been joined to any other branch (say) for which the a+b-c value is larger, that route would 640 not be the shortest route. Also every segment (It may be any segment not only the adjoining 641 segment) is joined to its nearest segment via a+b-c-d rule. The reason for above is same as of 642 property one. 643 .If every point is joined to the nearest branches respectively and no further alteration in the 644 position and order produces further shortening of route, we can safely conclude that the route 645 indeed the shortest. Our method produces the shortest route because it is based on the 646 properties which make the shortest route the shortest. We can end by continuous application of 647 properties 1 and 2 only at the shortest route. 648 This condition is reached when conditions (properties) 1 and 2 are satisfied. 649 Hence these two properties are the necessary and sufficient conditions for a shortest route to be 650 the shortest. 651 The method which we have used gives after each step a decreasing sequence of shorter routes 652 and in the end this decreasing sequence terminates at the shortest route. 653 Hence the route achieved is the shortest indeed as if a shorter was possible it would have come 654 in the decreasing sequence of repeated application of property 1 and 2. 655 656 657 658 659 7. FINAL CONCERNS ABOUT THE OPTIMAL TOUR Page 20 of 26 We have so far developed a method to find the optimal tour between the 660 above points and also 661 tried to establish that this route is indeed the shortest, but one query arises that this route may 662 be a local optimal tour and not a general optimal tour! 663 The concern arises only due to the fact that the tour may not be the optimal tour and a better 664 tour may exist and our tour may be optimal locally not universally. So this section attempts to 665 prove that our tour is a universal optimal tour and not a local optimal tour. So let us draw a 666 comparison from no other than the Mr. optimal tour itself. Fig. 8 presents two hypothetical 667 tours, Fig. 8(a) is a hypothetical universal optimal tour and Fig. 8(b) may be thought as a local 668 optimal tour which may be got by many of the known methods or by our method, say! 669 So let us take a singularity and see whether in it arises in our method or not. 670 Space for Fig. 8(a) and 8(b) 671 672 673 674 675 676 677 678 679 680 681 682 Now as obvious from the above Fig.8 (a) & 8(b), Fig.8 (a) is the hypothetical local tour and 683 Fig.8 (b) is the hypothetical optimal tour which we got by our method. We will see that whether 684 these two are same or there may be a condition which may remain unturned by our method. So 685 we try to list the differences which may remain when our method is completed. As you will 686 recall that we got an optimal tour by series of steps. But it may still happen that a point may be 687 joined to a side which is not in the mesh i.e. it is not present till now, for example, P1P2 is a 688 diagonal which may exist in the optimal tour but not present in local tour. No other singularity 689 may be counted here after as if a point has to be joined with a side already present it would be 690 caught in the last check. Therefore only possible singularity seems to occur when a point is to 691 be joined to a side not already present. So if we apply hypothetical diagonals case well this may 692 be sorted out. Hence the hypothetical diagonal case makes all the difference and makes our 693 local optimal tour a universal optimal tour. Page 21 of 26 We would again emphasize that our tour is optimal tour 694 because it is generated by a 695 continuous process of improvement and it ends only when no point is left which is not joined to 696 its optimal branch. 697 698 699 700 701 702 8. FEW COMPARISONS WITH STANDARD KNOWN 703 HEURISTICS 704 This is a good time to compare applicability of our results with few of standard known 705 methods for finding a optimal tour in ETSP. These results are summarized at 706 http://www.research.att.com/~dsj/chtsp [A] and have been published as a report "The 707 Traveling Salesman Problem and its Variations,"Gutinand Punnen (eds), Kluwer Academic 708 Publishers, 2002, 369-443. 709 The heuristics which come to close calling with that of ours is nearest insertion (p 29,[A]).The 710 main differences are that we start with a standard convex polygon and our process of 711 improvements ends only when no correction can be made, equivalently when optimal tour is 712 reached. The cheapest insertion and convex hull cheapest insertion is also a similar method but 713 all these methods seem to have only one limitation that they stop after few steps and further 714 improvements are not made. Our possible heuristic seems to succeed only because it ends only 715 when an optimal tour is reached. The greedy method is the closest to our lowest sum method but 716 with a marked difference. In greedy method we cant always get all the branches in the tour and 717 the nearest branch at certain point may end the tour prematurely, else we deviate from our 718 greedy methods basic philosophy. Also the property 1 specifies that the points are joined to the 719 most optimal branch and it may happen that the nearest branch may not be the most optimal 720 branch. 721 722 723 724 725 9. ONE STEP CHECK FOR OPTIMAL TOUR 726 We have to this point tried to establish our point by the methods discussed before. To end 727 our proof we will use a method similar to mathematical induction, to show whether our 728 method will eventually lead to the optimal tour. For that to happen we take any optimal tour Page 22 of 26 or approximate optimal tour which we might get from any of the known 729 methods. We now 730 have an optimal tour which is say 2.5% of the optimal. If by our method we can improve or 731 upgrade it to one step further to a shorter route then we can use inductive reasoning to 732 establish that we can continue it till an optimal tour is reached. Now if we consider any 733 hypothetical approximate optimal tour and apply our method of checking all the point on the 734 existing net for being joined to their optimal branch, we can get a local optimal tour. Further 735 our case of hypothetical or virtual segments will give us another local tour, which can be 736 improved to a local optimal tour by our methods of segment to point and segment to segment 737 check. Therefore, essentially our method, by the process of local improvements give a series 738 of local optimal tours which eventually lead to universal optimal tour . Basically our method 739 has two kinds of improvements, one which is done on an existing network to get an local 740 optimal tour. Further another improvement method gives a series of local optimal tours 741 which lead to the ultimate optimal tour. The two improvements which we are discussing are 742 segment to point check, segment to segment check and virtual segments check. 743 Therefore we have the optimal tour in the end. If for any reasons whatsoever we arrive at a 744 junction when any of the corrections give no improvements then, indeed we have the optimal 745 tour. This only means that all the points are joined to their optimal branches. 746 747 We can define these as interior local improvements and exterior local improvements. The 748 interior local improvements are implemented when we compare all the points on a network 749 without changing the basic configuration or network. This simply means that we cannot 750 create a virtual segment in interior improvements. Hence in interior local improvements we 751 can always reach at our starting point, if we wish. On the contrary in an external 752 improvement we change the network via a virtual segment and any of the interior local 753 improvements cannot take us back to our original network, without using a segment 754 correction. Therefore our method has two step improvements which smake it different and 755 possibly more effective than other known methods. 756 757 758 10. ALGORITHM/ HEURISTICS FOR FINDING THE 759 SHORTEST ROUTE 760 Step 1: Find the largest outer mesh which has maximum points lying on a SCP. 761 Step 2: Using a+b c rule find the points which belong to this network in the sense that they 762 are nearer to the net work than themselves. 763 Step 3: Find the other networks in which points are nearer to themselves. 764 Step4: By repeated application of step 1, 2 , 3, find all such networks. 765 Step5: Apply the case of hypothetical diagonals to get a shorter route. 766 Step5: Join these networks by segment to segment rule i.e. a+ b-c- d rule. 767 Step6: Apply segment test to get further reduction. Page 23 of 26 Step7: Perform the last check for all points and segments. Re apply 768 step 5 for any further 769 corrections needed. 770 Step8: The route is the shortest route i.e. the tour is the universal optimal tour.. 771 772 773 774 11. MATHEMATICAL EQUIVALENCE 775 We will now establish that the above working requires no more than fourth degree polynomial 776 time. 777 We have to make two types of calculations 778 a + b c 779 a + b - c d 780 Now there are n.C(n,2) segments which account for various c subtractions also their are n 781 points for a + b. 782 . Maximum calculations could be 2. n.C(n,2) as for one point and one segment we have two 783 calculations. 784 For n points we have 2n calculations. Similarly for C (n, 2) segments we have in total 2n.C(n,2) 785 calculations 786 787 On similar grounds number of calculations for segment to segment are 788 2 .C(n,2).C(n,2) 789 Order of polynomial P is 790 P =2n. C(n,2)+ 2. [C(n,2)]2 791 . C.n4 + C .n3 792 . C .n4 = O(4) [Order 4] 793 Further for one point if we have to do these number of calculations i.e. to place one point to its 794 nearest branch for a total on n points the total number of calculations would be of the order 795 n.Cn4 = Cn5 =O(5) [Order 5] 796 .Hamiltonians path problem is solvable in polynomial time of fifth degree at most. 797 Note the term nearest has special significance here. We join a point to a branch only if it is 798 the nearest to it, otherwise we leave it till it is joined to the better places of the network. This 799 method is useful particularly to avoid branches which need to be modified later. So this careful Page 24 of 26 selection of right points at each step is the basis of success of the method 800 described. One last 801 point about the tour being optimal, after each step we reject C(n, 2) longer tours. In next step we 802 again reject approximately C(n,2) tours. Note that the total tours rejected are C(n,2).C(n,2) 803 i.e.C(n,2)2 but total calculations are 2.C(n,2).Hence in n steps we reject C(n,2)n (dont bother 804 many tours are common!) but total calculation are no more than n.C (n,2).Mathematically 805 speaking with a check of polynomial origin we can effectively check tours of the range on non 806 polynomial nature. The method succeeds only because it tries to transform multiplication 807 involved in the formulation of solution (that is listing of all possible tours) to addition. 808 809 810 811 812 12. FEW COMPARISONS WITH ACTUAL SOLUTION 813 -A DEEPER INSIGHT 814 Let us now examine few actual solutions and see whether they meet our methods and 815 criteria which we have specified .We would take one of the famous tours namely the optimal 816 tour through 24,978 cities in Sweden [Link to it is provided at the end under the section of 817 references, links and further reading]. Apart from the symmetry we can at once point out that 818 it has two basic properties. To start with we can at once point out that the map has an outer 819 mesh which is a convex polygon or a distorted convex polygon .Further the inner networks 820 seems to be formed of a lot of independent networks. But the most important point is that we 821 can prove with the help of this network efficiency and working of our method. We can easily 822 point out that our two properties of shortest route are satisfied here. Each of the point is joined 823 to the nearest branch and also each segment is joined to the nearest segment. We also see that 824 no other property than these are either applicable or required to this network to be the 825 shortest route. We can also prove that our method of finding the shortest route is polynomial. 826 Suppose we distort this network and reach at a point in which m points are not joined to their 827 nearest branches, m<n obviously. Now from here we start checking for each point. In less than 828 C(n,2) tests we can find the nearest branch to the point and by joining other points to their 829 second nearest ones we can find whether this change is acceptable or not. So in one step we can 830 find the nearest branch for that point. So after each step one point gets eliminated, and in no 831 more than m steps we get a route which is the shortest with respect to the points. The order of 832 this calculation is n.C(n,2) i.e. 3.The same result is for segment to segment connections. The 833 point to notice is that after each step we discard around C(n,2) routes barring just one. So in 834 total n steps we discard about [C(n,2)]n ways. Since many routes are common this number 835 well exceeds the total number of routes. The point to note is that since we are discarding the 836 routes in steps we need only n steps but total number of discarded routes is much more as Page 25 of 26 total number of routes is obtained by multiplying. Hence the total routes 837 are Non- polynomial 838 as they occur as a product function and total number of steps is polynomial as they are sum 839 function. Thats the basic difference in this method and brute- force method. Our method uses 840 sum function and brute- force method uses product function. Hence the result. 841 842 843 844 13. FURTHER PROGRESS AND CONSEQUENCES 845 The progress from here has amazing consequences. The public key- cryptography may become 846 more vulnerable to break but it does tell us drawbacks of our system. Also the proof opens 847 search for a polynomial time solution to those 300 plus NP- complete problems. This also helps 848 us to focus our attention on the efficient and intelligent methods to solve problems than fast 849 methods. 850 851 852 THANKS AND GOOD BYE 853 HEMANT PANDEY 854 (SOLE AUTHOR) 855 Note: Figures are attached in another (Corel draw).pdf file with list of references. The 856 report [A] has also been attached for review purpose only. |