Comments about "P versus NP problem" in Wikipedia

This document contains comments about the document http://en.wikipedia.org/wiki/P_versus_NP_problem In the last paragraph I explain my own opinion.

Contents

Introduction

The article starts with the following sentence.
The P versus NP problem is a major unsolved problem in computer science.

The P versus NP problem is primarily a mathematical problem.
Next we read:
Informally, it asks whether every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer.
This is a very loose sentence. Twice the word efficiently is used. The whole issue is if they both mean the same.
Also why mention the word computer.
A more rigorous description is the following:
Informally, it asks if every problem for which there is a solution can be checked and solved by the same number of steps.
In most cases the answer is NO, because it is much simpler to test the answer than to find the answer.
The multiplication of 7 times 11 is 77. Both 7 and 11 are prime numbers.
To calculate the numbers 7 and 11 when you know the number 77 (this is called factorization) is a rather complex problem. To test the answer is simple.
Next we read:
The informal term quickly used above means the existence of an algorithm for the task that runs in polynomial time.
The most important issue is that in both cases the word quickly means the same i.e. the same duration.
The general class of questions for which some algorithm can provide an answer in polynomial time is called "class P" or just "P".
See for an overview of all different types of algorithms in Wikipedia: Time complexity
Next we read:
The class of questions for which an answer can be verified in polynomial time is called NP.
Next is written:
Consider the "subset sum" problem an example of a problem that is easy to verify, but whose answer may be difficult to compute.
hence this problem is in NP (quickly checkable) but not necessarily in P (quickly solvable).
In every problem if you give help you modify the original problem and you make the problem easier. The problem becomes the easiest if you give the answer. Next we read:
An answer to the P = NP question would determine whether problems like the "subset-sum" problem that can be verified in polynomial time can also be solved in polynomial time.
This sentence is rather tricky and unclear. Why mention: "like the "subset-sum" problem" ?
If it turned out that P does not equal NP, it would mean that some NP problems are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time.
I expect that most problems are that way.
This is the case with the "subset-sum" problem"
Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing and many other fields.
Nonsense. How can a proof either way have profound implications ?

1. Context

The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (# of steps) and space (memory).
Why mention all of this?
In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic and sequential.
Again why mention this?
In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine
Why mention deterministic versus non-deterministic machine?
A computer, executing a program, using the same inputs always gives the same answer.
Is P equal to NP?
In a 2002 poll of 100 researchers, 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and therefore is impossible to prove or disprove.
It would be interesting to know exactly what the questions of the poll are.
IMO the fact of this wide range of answers implies that exactly what "P" and "NP" means is not clear. The same feeling you get when you read the whole document

2. NP Complete

NP-complete problems are a set of problems to each of which any other NP-problem can be reduced in polynomial time, and whose solution may still be verified in polynomial time.
It is important to remark that the word polynomial time is used, which is a very "loose" concept
NP-hard problems are those at least as hard as NP problems, i.e., all NP problems can be reduced (in polynomial time) to them. NP-hard problems need not be in NP, i.e., they need not have solutions verifiable in polynomial time.
The distinction between NP-complete and NP-hard is very subtle.

5. Does P mean "easy"

In this paragraph we read:
There are algorithms for many NP-complete problems, such as the knapsack problem etc that can solve to optimality many real-world instances in reasonable time.
Also the knapsack problem is as easy to solve as to check.
All problems that require optimization require that in order to check a given solution you must be able to solve the problem.

7. Consequences of solution

A little further we read:
For instance, the decision problem version of the travelling salesman problem is NP-complete.
The "Travelling salesman problem" which tries to find the shortest distance of a string which connects all points is also a problem which takes the same amount of steps to solve as to check. Of course it is easy to check the length of a solution but it is difficult to verify if this answer is correct (i.e. is the shortest route). See also Reflection.

8. Results about difficulty of proof

In this paragraph we read:
The Clay Mathematics Institute million-dollar prize and a huge amount of dedicated research with no substantial results suggest that the problem is difficult.
The reason is because the prize by the Clay Mathematics Institute is very vaguely stated: "determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure."
What means "impossibly long" etc. etc. See also the start of this article. Next we read:
Some of the most fruitful research related to the P = NP problem has been in showing that existing proof techniques are not powerful enough to answer the question, thus suggesting that novel technical approaches are required.
This all smells to science fiction.
The Clay Mathematics Institute contest is more a contest without instructions. The winner is the Institute.

Reflection

The whole challenge of the "Travelling salesman problem" is to find the simplest (shortest) algorithm to solve the problem. That means the issue is to solve problems. To check the solution and how difficult that is, is no issue.

Chess is a typical example which belongs in the category difficult to solve and difficult to check. The computer can tell you what the best solution is, but to check that you have to execute the algorithms involved. In stead of difficult you can also write efficiently

The question: "what are the two prime numbers that you get when you multiply them and the answer is 143", is a simple question. The difficulty of the problem depends about the size of the prime numbers involved. With difficulty I mean (computer) time to find the solution and not so much the complexity of the calculations involved.
If I tell you that one answer is 11 than the problem becomes easier to solve and to find the second number i.e. 13. I specific write here to solve want in fact if I give you part of the answer (i.e. help) I have modified the original problem.

In short IMO this whole topic (to solve versus to check) is rather irrelevant.

Feedback

Read: Nature News: Million-dollar problem cracked? At the end there is a comment by the author.

If you want to give a comment you can use the following form Comment form
Created: 23 August 2010

Back to my home page Index