Edward R. Pratowski P≠NP November 2, 2008
P ≠ NP
Polynomial Time Problems are not the same as Non-Deterministic Polynomial Time Problems
Abstract
Computers, being deterministic machines, can solve problems where the processing time is directly related to the size of the data. Such problems are called “polynomial time” (or “P” for short). Other problems, “non-deterministic polynomial time” (or “NP” for short), seem to involve more data and computation than would be practically computable. If someone could translate a problem of type NP into a problem of type P, then the main obstacle to solving that problem would be computation time. Some people have proposed that such translation may be possible for all NP problems, implying that P = NP. This paper will show that NP problems are essentially different from P problems, thus P ≠ NP.
Polynomial Time Problems (P)
When classifying a problem according to its difficulty, we find that we can solve some problems on a deterministic machine (computer). Even the best computer can only perform a finite number of calculations per second. When the calculation time is directly related to the number of necessary calculations, we can call this polynomial time. How many ways can a person travel between two cities, given a very loose time constraint? This question is an example of a “P” problem. If we expanded the question to include three cities, the problem would get increasingly difficult – only because of the increased number of possible routes that the computer would have to calculate.
Non- Deterministic Polynomial Time Problems (NP)
Some polynomial time problems involve so many calculations, that even a group of the best deterministic computers could not perform all of the necessary calculations in a human’s lifetime. If a computer could have a “lucky guess” (or something like that), then that computer would be non-deterministic. When considering all possible routes among three cities, a deterministic algorithm might be time-consuming but possible to calculate. When considering all possible routes among a hundred cities, as a travelling salesman might do, the amount of data becomes overwhelming and time-prohibitive.
NP Completeness
A problem is NP complete if the solution to this problem might lead to a solution for other such problems. For the focus of this current paper, a more detailed definition is not necessary.
P ≠ NP Proof
Here is a proof, by counterexamples, that we can not reduce all NP problems to type P. I will call these types of problems “human” problem, because they require a perspective that a human can provide.
More and more web sites and other services claim to have an algorithm that will find a romantic match for a person. When considering one person’s (even vague) criteria against billions of possible matches, the computation time is considerably long, and a non-deterministic “lucky guess” would help; therefore, we can consider this problem to be NP. Even after successively narrowing down the possible matches for a person, the match might not be a success. For such a problem, anyone could easily check the success of the solution; however, no computer algorithm could consistently solve the problem.
As for the famous travelling salesman problem, any human with a map could solve that problem in five minutes. If the salesman had to visit more than 100 cities in the United States, he could mark a dot on the map for each city and draw a line connecting the dots in an efficient route.
The Hamilon circuit problem is a puzzle that some young students do in math classes. Some people find this problem rather easy, while some others may find it difficult. The important aspect of the problem is that it requires a human concept of “the big picture,” something that machines can not do.
Some web sites, such as Ticketmaster.com, contain their own version of a Turing test. The user must look at a distorted image of a word and type (in a text box) what the word is. Computers can not perform this task. Imagine the same test involving only one letter. As a polynomial time problem, we could say that the computer could test all possible distortions of every letter to determine which letter is displayed. Adding more letters would increase the difficulty of the task, until the calculations became too much to do in any reasonable time; and as an NP problem, we could say that a lucky guess may be possible.
Discussion
The concept of “non-deterministic” does not simply refer to a “lucky guess” as a means of solving NP problems; the concept refers to the fact that a deterministic system can not solve such problems. To counter the “NP Completeness” concept, we can remember Godel’s Incompleteness theorem: sometimes a different system is required to solve the problem. Some (perhaps many) NP problems require a “big picture” perspective or human insight – not luck – to find a solution. Semiconductor-based technology can not solve every problem, just as human insight can not solve any problem; however, the combination of the two could probably solve almost any problem that exists.
References
2