NP-Completeness

Complexity Recap

Assuming one already knows what algorithmic complexity is, I am writing this paragraph to explain it to those who don't. The complexity of an algorithm can be measured by its efficiency. So let's say I have a problem P for which I've proposed two algorithms A and B as solutions. How could I determine which algorithm is the most efficient in terms of time and data support? Well, by using complexity ( space complexity and time complexity ). One way of measuring complexity is O notation.

 Exponential Complexity O(2^n)

In algorithms, this complexity arises when the time or space required for computation doubles with each additional element in the input. Problems with exponential complexity are typically NP-hard or NP-complete

P-Class and NP-Class

• The P-class represents the set of polynomial problems, i.e., problems for which a solution can be found in polynomial time.
• The NP-class represents the set of non-deterministic polynomial problems, i.e., problems for which a solution can be verified in polynomial time. This means it's easy to verify if a proposed solution is correct, but finding that solution might be difficult.

P = NP Question?

The question of whether P is different from NP is one of the most important problems in theoretical computer science. It is part of the seven problems selected by the Clay Institute in the year 2000, for which a reward of one million dollars is offered to whoever solves them.

NP-Complete Problem Class

NP-complete problems are problems that are both in the NP-class and are harder than all other problems in the NP-class.Solving any of these problems would be considered a major breakthrough in theoretical computer science and could have a significant impact in many areas such as optimization, planning, cryptography, etc. There is no specific monetary reward associated with solving an NP-complete problem, but it would be considered a significant achievement.

Link to the NP-complete problems list

From an NP Problem to Another 

A polynomial reduction is a process that transforms an instance of one problem into an equivalent instance of another problem. In the case of polynomial reduction between NP-complete problems, this means that if you can efficiently solve problem B, then you can also efficiently solve problem A. This leads to the fact that if only one problem is solved from the list, then all the other problems will also be solved.

Approximation Algorithms

Computer scientists have devised approximation algorithms to efficiently solve NP-complete problems, even if finding an exact solution in polynomial time is not possible. These algorithms seek to find a solution that is close to optimality, although it may not be the optimal solution.

We can divide them into two categories:

• Heuristics: These are explicit algorithms that propose solutions for NP-complete problems.
• Metaheuristics: Unlike heuristics, metaheuristics are general strategies that guide the search for a solution without prescribing a specific algorithm.