Analysis of the Status of the P versus NP Problem Article by Lance Fortnow - Essay Example

With innovations in computational power, there has been an increase in algorithms that are much smarter than before. Under such circumstances, the pressure to tackle the P versus NP problem is considerably increasing. Moreover, this P versus NP problem is invading all fields of science as just not a theoretical question but as a basic principle. The author of the article surmises herein, the simple description of the issue and the change in a working direction related to computer science attained because of efforts to solve this question.

P versus NP problem computes combinational issues. Jack Edmonds, first in history, provided a program that can help in developing a program to solve combination problems, and formally defined it as ‘efficient computation’. P in this problem stands for ‘Polynomial Time’ and defines a problem class that has an efficient solution. Likewise, NP in this problem stands for ‘Nondeterministic Polynomial-Time’ and refers to the problems that have solutions that can be verified efficiently.

Furthermore, author describes that extremely complicated NP problems are termed ‘NP-complete’ problems. Examples of such problems are Clique, Partition and triangles, 3D-coloring, and Hamiltonian cycle. The idea promoted by NP-complete asserts that if an efficient algorithm can be developed for one problem, it can also be developed for other complicated problems too. Thus to simplify, P defines the type or the category of the problem that comes with an efficient solution whereas, NP defines a group of problems, each of which has an efficient recognizable solution.

By saying P = NP, we mean to say that for any problem that has an efficient verifiable solution, we can efficiently identify that solution. However, many scientists believed that P ≠ NP and defined it as the inability to find the solution efficiently. The author presents several attempts to prove a problem that is opposite to the original P versus NP problem. This problem states that P ≠ NP, however, the author has failed in all his attempts to prove it. Among the tried approaches to show P ≠ NP, the author enlists diagonalization, circuit complexity, and proof complexity.

As to prove P ≠ NP, diagonalization requires simulation. While we don’t have any evidence to simulate an arbitrary P from a fixed NP, therefore, this approach fails. The ever-increasing circuit complexity also defines limitations to approving P ≠ NP, as the complete collection of NP cannot be selected from small circuits. Similarly, the attempt to prove complexity fails to prove that P ≠ NP as Boolean-formula satisfactory condition cannot be solved in near-linear time. It also becomes evident that any problem can’t be resolved at the same time by utilizing the same memory.

The author concludes that as much as the P versus NP problem is inspiring our minds, the continued exploration of this problem will lead us to increase the complexity of computational analyses.ReferenceFortnow, L. (2009). The status of the P versus NP problem.