A little more about P and NP

There is a big difference between difficult tasks and complex tasks. A task may not have effective solutions in the worst cases, but it can remain easily solved for most cases, or for cases that arise in practice. Therefore, generally accepted definitions of task complexity may turn out to be relatively meaningless in terms of real complexity, since two tasks can be NP-complete, but one in most cases can be solved quickly and the other not. As a result, the concept of “average complexity” plays an important role in complexity theory (here, “average” is the mathematical expectation of the solution time).

To illustrate the central role of this concept, one can imagine five different possible worlds (possible - because it has not yet been proved that they are unrealistic, and ours can turn out to be any of them) and see how the conditions in them will affect computer science and life in general.
In particular, to demonstrate from a human point of view, we will use the sad story of Professor Groes, the very teacher of mathematics who asked the class a task - to count the sum of numbers from 1 to 100. Everyone knows that little Gauss was in his trouble in the class, who quickly I noticed the regularities of arithmetic progression and almost instantly calculated this amount. But few people know that after this, the Professor was obsessed with the obsession with revenge on Gauss and humiliate him in front of the whole class, coming up with tasks that Gauss could not solve. This led the Professor to a madhouse (not the most pleasant end, especially in the 19th century), and Gauss developed an interest in number-theoretic algorithms. Let's try to imagine what would happen in the different worlds that we will consider.

Algorithm

Algorithmics is a world in which P = NP. In this world, the Professor would be even less fortunate than in reality. Since the Professor needs to baffle Gauss with a task to which he (the Professor) must then show the class the correct answer, he is limited in the choice of tasks to those that have an easily verifiable solution (that is, problems from NP). Gauss can use the verification method to automatically solve this problem.
The method of automatically obtaining an algorithm for solving problems from an algorithm for verifying the correct solution will revolutionize the computer science of that world. Tasks that seemed unsuitable will be trivial. Almost all optimization tasks will be simple and automatic. For example, heuristics will no longer be used in VLSI design; instead, optimal wiring will be generated if an optimality criterion is specified. Programming languages ​​will no longer contain instructions describing how to perform calculations. Instead, they will only describe the properties that the output should have in relation to the input. The compiler will independently translate the specification language into a decision algorithm.
Less obvious is that P = NP will make many aspects of artificial intelligence trivial. Learning systems based on the Occam Razor principle can be used to automatically train a computer to perform actions that people can do. It will be enough to provide a training sample of input data and output data produced by a human expert, and the computer will output a simple algorithm that will produce the same answers as the expert. So, a computer can be taught to recognize and parse sentences in a natural language, you only need to provide a sufficient number of examples of true and false sentences (here it is assumed that there is some simple algorithm that people use to parse natural languages).
On the other hand, in Algorithmics it will not be possible to distinguish between people and computers from an information point of view. Mentioned learning algorithms can easily learn to mimic the behavior of other machines and even people. Any code that can be developed can just as easily be cracked. It will be of little use to try to hide the algorithm on which the code is based, since the same algorithm can be easily obtained by having a small number of ciphertext-playtext pairs. It will not be possible to provide access to information to several people, without making it thus accessible to all. Therefore, any identification methods will have to be based on physical measurements.

Heuristic

Heuristics is a world in which problems from NP do not have effective solutions in the worst case, but are easily solved on average (for some probability distribution on multiple inputs).
Heuristics, in a way, is a paradoxical world. There are complex instances of tasks from NP, but finding such a complex instance is a difficult task in itself. In this world, the Professor will be able to find tasks that will be too tough for Gauss. But he will have to spend a week searching for a task that Gauss cannot solve during the day, and a year to find a task that Gauss will spend a month (in this case, it is assumed that Gauss has some polynomial advantage over the professor, because Gauss, in the end of genius). Most likely, life is not so severe as to provide us with complex tasks, if only life does not seem raspberry. Therefore, for practical purposes, this world is almost indistinguishable from Algorithmics.
Or is it still distinguishable? In Heuristics, the average time to solve a problem from NP depends on the average time to “think over” this problem. This complicates the situation somewhat. Suppose, on average, computing a solution to a problem is two times longer than inventing a solution. If we spend time T on thinking over problem No. 1, then we will spend 2T time units on calculating the solution. The solution to this problem affects the solution to problem No. 2, i.e. We spent 3T units of time thinking about the solution to Problem 2. Therefore, 6T units of time will be spent on solving problem No. 2. Which leads to problem number 3, which we have already spent 10T units of time thinking, therefore 20T will be spent on the solution. As this recursion grows exponentially, in just a few steps we will cross the border between “feasible” and “unreal”.
In the case of VLSI design, there will no longer necessarily be effective solutions, since in this case we are not very interested in most of the possible schemes suitable for the specifications, and the minimum options that satisfy the specifications are important. Such schemes may not have a good distribution, and since it will most likely take exponential time to find them, there is no guarantee that they are not the “worst cases” on which the algorithms in Heuristic do not work well.
In cryptography and network security there will be no fundamental differences with Algorithmics. It would be of little use if conscientious users spend a lot of time searching for an instance of a task that could uniquely identify them, when an attacker can solve this instance in a comparable amount of time (it is assumed that an attacker who wants to crack the system uses significantly more resources than conscientious user).

Pessilandia

Pessilandia is the worst possible case - it has tasks that are difficult to solve even on average, but there are no one-way functions. By the absence of one-sided functions we mean the following: for any problem that is easy to calculate, it is also easy to find a solution to the inverse problem, in the sense that for almost all values ​​of x, if F (x) is given, then we can find some x 'such that F (x ') = F (x), moreover, in about the same time that is spent on calculating F (x).
In Pessilandia, the Professor could ask Gauss problems that even a young genius could not solve. But the Professor himself could not have demonstrated the solution, so the humiliation of Gauss would be incomplete.
In this world, in many areas tasks would not have easy solutions. Progress would be the same as in our world: it would advance slowly through a deeper understanding of the world and through the use of not entirely satisfactory heuristics. General methods for solving problems would not work in most areas. However, several useful algorithms would be possible based on the absence of one-way functions. For example, a data compression method in which, knowing the distribution of the input data, in the limit it would be possible to compress them to the expected length in accordance with the distribution entropy.
In this world, it will not be possible to use complex tasks in cryptography. A task to which no one knows the answer cannot be used to distinguish a conscientious user from an attacker.

Minicrypt

The minicrypt has one-way functions, but public-key cryptography is not possible. Here, we mean by public key cryptography the task of secret communication through public communication channels, although, strictly speaking, public key cryptography is only one way to solve this problem.
One-way functions can be used to generate complex but solved problems, namely: the generator will choose x, calculate y = F (x) and set the search task to “find such x 'such that F (x') = y”. Thus, in the Minicrypt, the Professor will finally be able to defeat Gauss in front of the whole class.
On the network, participants will be able to identify themselves to other users, as well as authenticate messages using a digital electronic signature. It will be possible to prove facts about a secret without revealing other secret information contained in it. If a small amount of information is transmitted in advance between the participants, then you can set a reliable secret code between the two network participants, which will allow them to communicate behind closed doors, using open communication channels. However, it will not be possible to conduct a secret ballot through open channels, or to ensure secure negotiations without first sending some information through secure channels. It will not be possible to create anonymous digital money.

Cryptomania

In Cryptomania, public-key cryptography exists. In Cryptomania, Gauss will be humiliated even more; The professor and his favorite student will be able to jointly choose a task for which they both will know the answer, and Gauss will not be able to solve it. Moreover, in this world, the Professor will be able to make sure that everyone in the class knows how to solve a given problem, except for Gauss.
The existence of public key protocols implies the existence of one-way functions, therefore, pseudo-randomness, digital signatures, identification, zero-knowledge protocols and so on still exist in this world. Also, if a secret exchange is performed using one-way functions with a secret (and all known protocols use these functions explicitly or indirectly), any imaginable cryptographic tasks can be solved. Unlike other worlds where creating privacy is a technological challenge, technology in Cryptomania, on the contrary, will limit the ability of users to reduce privacy. Most decisions on how much confidentiality is allowed to citizens will be made as a result of political and social processes, and not because of technical capabilities.
This world is most similar to ours., At least as long as it is believed that well-known public key protocols are reliable.

R. Impagliazzo, " A personal view of average-case complexity ," sct, pp. 134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995

Image taken from XKCD .