Combinatorics and Graph Theory


P vs NP: Solutions of NP Problems

Authors: A. A. Frempong

Best news. After over 30 years of debating, the debate is over. Yes, P is equal to NP. For the first time, NP problems. including the classic traveling salesman problem have been solved in this paper. The general approach to solving the different types of NP problems are the same, except that sometimes, specific techniques may differ from each other according to the process involved in the problem. Another type of NP problems covered is the division of items of different sizes, masses, or values into equal parts. The techniques and formulas developed for dividing these items into equal parts are based on an extended Ashanti fairness wisdom as exemplified below. If two people A and B are to divide items of different sizes which are arranged from the largest size to the smallest size, the procedure would be as follows. In the first round, A chooses the largest size, followed by B choosing the next largest size. In the second round, B chooses first, followed by A. In the third round, A chooses first, followed by B and the process continues up to the last item. To abbreviate the sequence in the above choices, one obtains the sequence "AB, BA AB". Let A and B divide the sum of the whole numbers, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 as equally as possible, by merely always choosing the largest number. Then A chooses 10, B chooses 9 and 8, followed by A choosing 7 and 6; followed by B choosing 5 and 4; followed by A choosing 3 an 2; and finally, B chooses 1. The sum of A's choices is 10 +7+ 6 + 3 + 2 = 28; and the sum of B's choices is 9 + 8 + 5 + 4 + 1 = 27, with error, plus or minus 0.5 . Observe the sequence "AB, BA, AB, BA, AB". Observe also that the sequence is not "AB, AB, AB, AB, AB as one might think. Te reason why the sequence is "AB, BA AB, BA, AB" is as follows. In the first round, when A chooses first, followed by B, A has the advantage of choosing the larger number and B has the disadvantage of choosing the smaller number. In the second round, if A were to choose first, A would have had two consecutive advantages, and therefore, in the second round, B will choose first to produce the sequence AB, BA. In the third round, A chooses first, because B chose first in the second round. After three rounds, the sequence would be AB, BA, AB. When his technique was applied to 100 items of different values or masses, by mere combinations, the total value or mass of A's items was equal to the total value or mass of B's items. Similar results were obtained for 1000 items. By hand, the techniques can be used to prepare final exam schedules for 100 or 1000 courses. A new approach to solving the traveling salesman problem was used to determine the shortest route to visit nine cities and return to the starting city. The technique covered eliminates a shortcoming of the nearest neighbor approach as well as that of the grouping of the cities. The distances involved were arranged in increasing order and by inspection, ten distances were selected from a set of the shortest 14 distances, intead of the overall set of 45 distances involved. The selected distances were used to construct the shortest route. Confirmed is the notion that an approach that solves one of these problems can also solve other NP problems. Since six problems from three different areas have been solved, all NP problems can be solved. If all NP problems can be solved, then all NP problems are P problems and therefore, P is equal to NP. The CMI Millennium Prize requirements have been satisfied.

Comments: 33 Pages. Copyright © A. A. Frempong

Download: PDF

Submission history

[v1] 2014-08-28 23:13:13
[v2] 2014-08-31 12:03:19
[v3] 2014-09-05 15:45:29
[v4] 2014-09-13 17:03:27
[v5] 2014-09-17 00:14:25
[v6] 2014-12-14 17:17:00
[v7] 2015-05-23 02:41:45
[v8] 2015-05-23 11:39:08

Unique-IP document downloads: 528 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus