Over the years, the research community has divided problems into various categories according to their complexity. Before we attempt to design the solution to a problem, it makes sense to first try to characterize it. Generally, there are three types of problems:

• Type 1: Problems for which we can guarantee that a polynomial algorithm exists that can be used to solve them
• Type 2: Problems for which we can prove that they cannot be solved by a polynomial algorithm
• Type 3: Problems for which we are unable to find a polynomial algorithm to solve them, but we are also unable to prove that a polynomial solution for those problems is impossible to find

Let's look at the various classes of problems:

• Non-Deterministic Polynomial (NP): For a problem to be an NP problem, it has to meet the following condition:
  • It is guaranteed that there is a polynomial algorithm that can be used to verify that the candidate solution (certificate) is optimal.
• Polynominal (P): These are types of problems that can be thought of as a subset of NP. In addition to meeting the condition of an NP problem, P problems need to meet another condition:
  • It is guaranteed that there is at least one polynomial algorithm that can be used to solve them.

The relationship between P and NP problems is shown in the following diagram:

If a problem is NP, is it P as well? This is one of the greatest problems in computer science that remains unresolved. Millennium Prize Problems, selected by the Clay Mathematics Institute, has announced a 1 million dollar prize for the solution to this problem as it will have a major impact on fields such as AI, cryptography, and theoretical computer sciences:

Let's continue the list of various classes of problems:

• NP-complete: The NP-complete category contains the hardest problems of all NP problems. An NP-complete problem meets the following two conditions:
  • There are no known polynomial algorithms to generate a certificate.
  • There are known polynomial algorithms to verify that the proposed certificate is optimal.
• NP-hard: The NP-hard category contains problems that are at least as hard as any problem in the NP category, but that do not themselves need to be in the NP category.

Now, let's try to draw a diagram to illustrate these different classes of problems:

Note that it is still to be proven by the research community whether P = NP. Although this has not yet been proven, it is extremely likely that P ≠ NP. In that case, no polynomial solution exists for NP-complete problems. Note that the preceding diagram is based on this assumption.