P-class of problems and NP-class of problems

See, we are talking about the asymptotic complexity of problems. Only tasks that have a simple, unambiguous answer: "yes" or "no"are considered here. For example, "is there a substring" XYZ " in this string?". Problems like "find all permutations of a given set of numbers" like P/NP - problems are not considered, since the answer here is not yes/no.

Algorithms are often parameterized by the size of the input data. The run time of the algorithm in the general case is greater than it has to process more data. Denote n1, n2, ... - parameters describing the size of the input data, t(n1, n2, ...) - the maximum time of the algorithm on data of this length.

If it is known that t(n1, n2, ...) is bounded from above by a polynomial in the variables n1, n2, ..., the problem is called solvable in polynomial time. The class of such problems is denoted as P, they are considered computationally simple.

Now, what is the NP - problem?

Imagine that, that you have an algorithm with multiple branches (if-s, cycles), which consistently tests solutions, and as soon as it finds a suitable one, immediately ends the algorithm with shouts of " hooray, I found it!" For example, if we are looking for whether the character 'X' is in a given string, we can loop through to check if the first character matches X, then the second, then the third, and as soon as we find a match, we finish the job. So, imagine now such a machine that magically immediately goes to the desired iteration of the loop: to search for the character X in the string "ABCXYZ", it immediately checks in the 4th position, that is, where it is necessary! Such a magical machine is called a nondeterministic machine (for historical reasons) and, of course, does not exist in nature.

So, a problem is called NP - a problem if it is solved in polynomial time on this very cheater nondeterministic machine.

It is clear that every P is a problem NP - the problem: if we can solve it on a normal machine in polynomial time, then even more so on a cheater machine! The question arises: is it necessary to cheat? Maybe every problem that can be solved on a nondeterministic machine in polynomial time can be solved on a normal machine in polynomial time, too?

This is the famous P/NP - hypothesis: assume that there are problems that are without a nondeterministic machine in polynomial time don't solve it. But no one has yet been able to justify this strictly mathematically. The problem here is this: if we can't solve a problem in polynomial time, does it mean that it can't be solved in polynomial time, or are we just not smart enough and inventive enough?