P vs NP

Chapter 1: Understanding P vs NP

So, you must be wondering ‘What exactly is the P vs NP problem?’

One of the most profound and challenging questions in the history of mathematics and computer science was by Stephen Cook, the 'P vs NP Problem'. It questions ‘whether every problem whose solution can be quickly verified by a computer, can also be quickly solved by a computer?’. This problem has been recognized by the Clay Mathematics Institutes and was included among the seven Millennium Prize Problems, offering a prize of $1 million for a correct solution.

Fundamental Concepts

Class P

It consists of all decision problems that can be quickly solved in polynomial time by a deterministic Turing machine (i.e. theoretical model of computation). Polynomial time, denoted by (nk) for some constant k, signifies that the number of steps required to solve the problem grows as the polynomial function of the input size.

Consider a problem where you have to sort a list of numbers. Algorithms like merge sort and quicksort can solve the problem in polynomials, specifically O(n log n). Another example is finding the greatest common divisor of two integers using the Euclidean algorithm that runs in O(n log n) time.

Class NP

It consists of the decision problems where the given solution can be verified quickly in polynomial time by a deterministic Turing machine. Unlike Class P, where solutions can be found promptly, Class NP focuses on the verification process.

An example of an NP problem is the Sudoku puzzle. Given a completed Sudoku board, verifying that it meets the game’s rules can be done quickly but finding the solution in the first place takes time.

The core question here is whether every problem for which a solution can be quickly verified (NP) can also be quickly solved (P). In other words, is P equal to NP?

If P were equal to NP, it would mean that the problems currently believed to require an impractically long time to solve could be solved quickly! This would have an intense implication for fields such as cryptography, optimization, and algorithm design. Since many cryptographic systems rely on the difficulty of certain NP problems, so if these problems were to be solved quickly, the security of these systems would be compromised.

Conversely, P not being equal to NP affirms that some problems are inherently difficult to solve even if their solutions can be verified quickly.

Chapter 2: Mathematical Structure and Implications

1. Mathematical Formalism

Turing Machines

A mathematical model of computation that consists of an infinite tape and a head that can read and write symbols on the tape. The machine is programmed to act based on the current state and the symbol it reads. A deterministic Turing machine has a single set of rules that deterministically dictate its actions whereas a non-deterministic Turing machine can choose among multiple sets of rules.

Polynomial time

The algorithm runs in a polynomial time (i.e. a measure of computational efficiency) if its running time can be expressed as a polynomial function of the size of the input such as O(n), O(n^2), or O(n^3). Polynomial time is considered efficient because the running time grows relatively slowly as the input size increases, making the problem tractable for larger inputs.

2. NP-Complete Problems

The subsets of NP problems are at least as hard as any other problem in NP. A problem is NP-complete if it meets two criteria: it is NP, and every problem in NP can be reduced in polynomial time. This means that if any NP-complete problem can be solved quickly, then every problem in NP can also be solved quickly, proving that P equals NP.

One of the most famous NP-complete problems to arise is the Boolean Satisfiability problem (SAT). Given the Boolean formula, the SAT problem asks whether there is an assignment of truth values to the variables that makes the formula true. The Cook-Levin theorem proved that the SAT is NP-complete, making it the first known NP-complete problem.

Reductions

Reductions are a key concept in proving NP-completeness. It means that problem A can be reduced to another problem B if a solution to B can be used to solve A. All NP problems could have been solved efficiently if they could be reduced to an NP-complete problem in polynomial time.

3. Historical Attempts and progress

Many attempts have been made worldwide to solve the ‘P vs NP’ problem, but it remains unscathed. In 1972, Richard Karp identified 21 NP-complete problems contributing to the historical progress made and the continued exploration of the relation between P and NP by researchers around the world adds up to the overall progress.

Current research on the P vs NP problem explores various approaches such as circuit complexity, proof complexity, and the study of specific problem instances. Despite significant progress in understanding the structure and properties of NP-complete, the question of whether P equals NP remains open.

Conclusion

The P vs NP problem is a cornerstone for mathematics and theoretical computer science. It poses a question with far-reaching implications over numerous fields, understanding the fundamentals of P and NP, NP-completeness and the significance of polynomial time provides a foundation for appreciating the depth and complexity of this problem. While the solution is yet to be found, ongoing research and efforts continue to pave a path towards the solution.

Author: Ashutosh Yadav

Editor: Rohitashwa Kundu

Illustrator: Mallika Yadav

Reviewer: Bristi Paul

Note: The information presented in the above text is intended for educational purposes only. While it is emphasized as to not present individual opinions of the authors. Any such mention is purely figurative and does not represent HEIV's stance. Scientific facts are carefully scrutinized before they are published. Any similarity with existing literature is made with due credits by author for educational purposes only.