P versus NP
The P versus NP problem is one of the most important and unsolved problems in computer science.
Computational Complexity
Computational complexity is a measure of the difficulty (in terms of time, memory, or some other criterion) of running an algorithm.
Example: Sorting a list. Using the Quicksort algorithm, the complexity is n2n^2n2 in the worst case and nlog(n)n \log(n)nlog(n) on average, where nnn is the size of the input array.
Example: Finding a value in an unordered list.
Average: (N+1)/2 comparisons
Worst case: N
The linear search algorithm is an O(n) algorithm.
What is P vs NP?
The class P consists of problems whose solutions can be FOUND in polynomial time.
The class NP consists of problems whose solutions can be VERIFIED in polynomial time.
In other words, polynomial time can be O(N²), O(N⁷), or any polynomial complexity. The idea behind this classification is that these problems are considered "easy" in the sense that they can be solved with current computational capabilities.
What is the difference between finding a solution and verifying a solution?
Example:
To FIND A SOLUTION, we would need to test whether 4819 is divisible by 2, 3, 5, 7, 11, 13, 17—that is, checking which prime numbers divide it.
However, the inverse problem is much simpler:
With a basic pocket calculator, we can VERIFY that 79 × 61 = 4819.
All modern RSA encryption is based on this asymmetry!
A problem might be exponentially hard to solve, with complexity O(2^N) or O(N!), but still be easy to verify—which means it belongs to the NP class.
A deterministic machine refers to a Turing machine, an abstract model of computation. A non-deterministic Turing machine, on the other hand, behaves like a regular Turing machine but can explore an infinite number of branches in parallel.
In summary:
Class P: Polynomial time – FINDING the solution in polynomial time (P).
Class NP: Non-Deterministic Polynomial time – VERIFYING the solution in polynomial time (P).
(NP does not mean "Non-Polynomial" – don’t make this mistake!)
NP-Complete and NP-Hard
Clearly, P is contained within NP—since if it is possible to find a solution, it is also possible to verify whether a solution satisfies the problem.
However, in the Complexity Zoo, there are a few more entities. What are they?
NP-Complete and NP-Hard
NP-Complete – These are the hardest decision problems within the NP class.
A problem is NP-Complete if every problem in NP can be converted into it in polynomial time.
Examples: Traveling Salesman Problem, Satisfiability (SAT), Vertex Cover, etc.
See Karp’s 21 NP-Complete Problems for more examples.
In other words, imagine that we have an efficient solver (polynomial-time algorithm) for the Traveling Salesman Problem. Since every NP problem can be transformed into the Traveling Salesman Problem, solving it efficiently would mean that all NP problems could also be solved efficiently. If you solve one NP-Complete problem, you solve them all.
NP-Hard – These are problems that are at least as hard as NP-Complete, but they do not necessarily have solutions that can be verified in polynomial time.
Optimization problems that arise in real life, such as harvest optimization or forestry planning, often involve linear and integer variables with numerous constraints—these are typically NP-Hard.
Is P = NP or not?
The big question is whether P = NP or not. It might seem simple, but to this day, no one has been able to prove or disprove this statement.
There is even a $1 million prize for whoever solves the question. It is one of the seven Millennium Problems, promoted by the Clay Mathematics Institute.
🔗 Millennium Problems – Clay Mathematics Institute
The Clay Institute was inspired by the 23 problems proposed by mathematician David Hilbert in 1900, which, in one way or another, guided the development of mathematics in the following decades.
Regarding the Complexity Zoo, since solving the main question (P vs NP) is difficult, mathematicians focus on solving problems that can be addressed. This has led to the creation of various other definitions of computational complexity types.
Does Quantum Computing Solve It?
When new computing paradigms, such as quantum computing, emerge, understanding their potential helps define limits and expectations.
In the case of quantum computing, it is believed to be more powerful than class P, but not capable of solving all NP problems. It may also be able to solve problems beyond the NP class.
Actually, just because a problem is polynomial doesn't necessarily mean it's easy. A problem with complexity O(N⁹⁹⁹⁹) would still be extremely difficult to solve.
On the other hand, NP-complete problems with small input sizes can indeed be solved with current computing power. In practice, modern solvers have made previously intractable problems at least minimally solvable for real-world applications. Thanks to advancements in hardware and software, it's possible to handle NP-Hard problems, at least a significant portion of them.
Well, in any case, there's a $1 million prize for anyone willing to dive deep into the topic! Just don’t win and refuse the prize like Grigori Perelman did (see the link below)!
#Operations research
