Combinatorics and Graph Theory

1505 Submissions

[2] viXra:1505.0175 [pdf] submitted on 2015-05-24 23:28:45

A Note on Erdős-Szekeres Theorem

Authors: M. Romig
Comments: 4 Pages.

Erdős-Szekeres Theorem is proven. The proof is very similar to the original given by Erdős and Szekeres. However, it explicitly uses properties of binary trees to prove and visualize the existence of a monotonic subsequence. It is hoped that this presentation is helpful for pedagogical purposes.
Category: Combinatorics and Graph Theory

[1] viXra:1505.0167 [pdf] replaced on 2015-05-28 23:37:40

P vs NP: Solutions of the Traveling Salesman Problem

Authors: A. A. Frempong
Comments: 14 Pages. Copyright © A. A. Frempong. Paper has been included in vixra:1408.0204 (Example 7 of P vs NP: Solutions of NP Problems by the author)

For one more time, yes, P is equal to NP. For the first time in history, the traveling salesman can determine by hand, with zero or negligible error, the shortest route from home base city to visit once, each of three cities, 10 cities, 20 cities, 100 cities, or 1000 cities, and return to the home base city. The formerly NP-hard problem is now NP-easy problem. 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. The first step is to arrange the data in the problem in increasing or decreasing order. In the salesman problem, the order will be increasing order, since one's interest is in the shortest distances. The main principle here is that the shortest route is the sum of the shortest distances such that the salesman visits each city once and returns to the starting city. The shortest route to visit nine cities and return to the starting city was found in this paper. It was also found out that even though the length of the shortest route is unique, the sequence of the cities involved is not unique. Since an approach that solves one of these problems can also solve other NP problems. and the traveling salesman problem has been solved, all NP problems can be solved, provided that one has an open mind and continues to think. 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..
Category: Combinatorics and Graph Theory