Cook's theory. A million dollars to think about. The fate of the remaining millions

Latest science news

$1 million prize for solving each of seven math problems
(based on materials from the site http://www.claymath.org./prize_problems/index.htm)

CMI - The Clay Mathematics Institute (Cambridge, Massachusetts) - named seven unsolved mathematical problems - "Millennium Prize Problems", for the solution of each of which $1 million will be paid. Solutions that were published in a well-known mathematical journal are accepted for consideration, and not earlier than 2 years after publication (for comprehensive consideration by the mathematical community).

Let's list these problems:

Cook's problem(formulated in 1971).
Let's say, being in a large company, you want to make sure that your friend is there too. If they tell you that he is sitting in the corner, then a split second is enough for you to take a glance and be convinced of the truth of the information. In the absence of this information, you will be forced to walk around the entire room, looking at the guests.
In the same way, if someone tells you that the number 13717421 can be represented as the product of two smaller numbers, it is not easy to quickly verify the truth of the information, but if you are told that the original number can be factored into 3607 and 3803, then this statement is easy checked using a calculator.
These examples illustrate a general phenomenon: solving a problem often takes longer than checking the correctness of the solution. Stephen Cook formulated the problem: can checking the correctness of a solution to a problem take longer than obtaining the solution itself, regardless of the verification algorithm.
This problem is one of the unsolved problems of logic and computer science. Its solution could revolutionize the fundamentals of cryptography used in data transmission and storage.

Riemann hypothesis(formulated in 1859).
Some integers cannot be expressed as the product of two smaller integers, such as 2, 3, 5, 7, etc. Such numbers are called prime numbers, and they play an important role in pure mathematics and its applications. The distribution of prime numbers among all natural numbers does not follow any pattern, but the German mathematician Riemann (1826-1866) discovered that the number of prime numbers not exceeding , is expressed through the distribution of nontrivial zeros of the Riemann zeta function. Riemann put forward a hypothesis, which has not yet been proven or disproven, that all non-trivial zeros of the zeta function lie on a straight line. To date, the first 1500000000 solutions have been tested.

Birch and Swinnerton-Dyer conjecture.
Mathematicians have long been fascinated by the problem of describing all integer solutions to algebraic equations, that is, equations in several variables with integer coefficients. An example of an algebraic equation is the equation. Euclid gave a complete description of solutions to this equation, but for more complex equations obtaining a solution becomes extremely difficult (for example, proving that there are no entire solutions to an equation).
In 1970, Yuri Vladimirovich Matiyasevich gave a negative solution to Hilbert’s tenth problem, i.e. There is no algorithm that can be used to find out whether an equation is solvable in integers or not. But in the special case where the solutions form an Abelian variety, Birch and Swinnerton-Dyer suggested that the number of solutions is determined by the value of the zeta function associated with the equation at point 1: if the value of the zeta function at point 1 is 0, then there are an infinite number of solutions, and vice versa, if not equal to 0, then there is only a finite number of such solutions.

Hodge's conjecture.
In the twentieth century, mathematicians invented powerful methods for studying the shape of complex objects. The basic idea is to find out to what extent we can approximate the shape of a given object by gluing together simple bodies of increasing dimension. This method has proven effective in describing a variety of objects encountered in mathematics. Unfortunately, the geometric rationale for the method was not clear: in some cases it was necessary to add parts that had no geometric interpretation.
Hodge's conjecture is that for particularly good types of spaces called projective algebraic varieties, the so-called. Hodge cycles are combinations of objects that have a geometric interpretation - algebraic cycles.

Navier-Stokes equations.
If you sail in a boat on a lake, waves will arise, and if you fly in an airplane, turbulent currents will arise in the air. It is assumed that these and other phenomena are described by equations known as the Navier-Stokes equations. The solutions to these equations are not known, nor is it even known how to solve them. It is necessary to show that a solution exists and is a sufficiently smooth function. Solving this problem will significantly change the methods of carrying out hydro- and aerodynamic calculations.

Poincaré problem.
If you pull a rubber band over an apple, you can, by slowly moving the band without lifting it from the surface, compress it to a point. On the other hand, if the same rubber band is suitably stretched around a donut, there is no way to compress the band to a point without tearing the tape or breaking the donut. The surface of an apple is said to be “simply connected,” but the surface of a donut is not. Poincaré knew almost a hundred years ago that in the two-dimensional case only the sphere is simply connected, and he asked a similar question for the three-dimensional sphere - a set of points in four-dimensional space equidistant from some point. It turned out to be so difficult to prove that only the sphere is simply connected that mathematicians are still looking for the answer.

Yang-Mills equations.
The equations of quantum physics describe the world of elementary particles. Almost fifty years ago, physicists Young and Mills, having discovered the connection between geometry and particle physics, wrote their equations. Thus, they found a way to unify the theories of electromagnetic, weak and strong interactions. The Yang-Mills equations implied the existence of particles that were indeed observed in laboratories around the world, including Brookhaven, Stanford, and CERN. Therefore, the Yang-Mills gauge theory is accepted by most physicists, despite the fact that within the framework of this theory it is still not possible to predict the masses of elementary particles.

The honor of being the "first" NP-complete problem goes to the recognition problem from Boolean logic, a problem commonly called SATISFACTION (abbreviated as SAT). The terms used to describe it are defined as follows.

Let U = (u 1, u 2, ..., um) be a set of Boolean variables. By a set of truth values ​​on a set U we mean a function t: U→(T, F). If t(u) = T, then we will say that u takes the value “true” relative to t; if t(u) = F, then we will say that it takes the value “false”. If u is a variable from U, then u and and are called literals from U. The literal and takes the value “true” relative to t if and only if the variable and takes the value “true” relative to t; literal and evaluates to true if and only if the variable “ evaluates to false.”

A disjunction over U is a set of literals over U, for example (u 1 , u 3 , u 8 ). It represents the disjunction of these literals and is said to be satisfied for a certain set of truth values ​​if and only if, for the considered set of truth values, at least one of its members evaluates to “true”. In our example, the disjunction will be satisfied with respect to t, unless it simultaneously turns out that t(u 1) = F, t(u 3) = T, t(u 8) = F. A set C of disjunctions over U is called satisfiable if and only in the event that there is a certain set of truth values ​​on the set U such that all disjunctions from C are simultaneously satisfied. Such a set of truth values ​​is called a fulfilling set of truth values ​​for C. The SATISFACTION problem is formulated as follows:

FEASIBILITY

CONDITION. Given a set of variables U and a set C of disjunctions over U.

QUESTION. Is there a satisfying set of truth values ​​for C?

For example, let U = (u 1, u 2) and C = ((u 1, u 2), (u 1, u 2)). This is an individual task from the VEP, the answer to which is “yes”. The task of truth values ​​is defined as follows: t(u 1) = t(u 2) = T. On the other hand, replacing C with C" = ((u 1, u 2), (u 1, u 2), (u 1)), we obtain an example of an individual task, the answer to which is “no”, since C is impossible. Cook's fundamental theorem can now be stated.

Theorem 2.2 (Cook's theorem). The task is FEASIBLEN.P.-complete task.

Proof. It is easy to see that VYP lies in the class NP. To solve this problem, a non-deterministic algorithm just needs to specify a set of truth values ​​on the original set of variables and check that this set of values ​​fulfills all the disjunctions from the original set C. All this is easy to do (in a non-deterministic manner) in polynomial time. Thus, the first requirement that NP-complete problems must satisfy is satisfied.

In order to check the fulfillment of the second requirement, let us return to the level of languages, i.e., to the representation of VYP in the language Lvyp = L[VYP, e] for some reasonable encoding scheme e. It is necessary to show that for all languages ​​L e NP the relation L holds ∞ Lvyp. Different NP languages ​​can be very different; the number of these languages ​​is infinite, so it is impossible to provide a separate summary for each of them. However, each language from NP can be represented in a standard form, namely by a NDMT program that runs in polynomial time and recognizes this language.

This representation makes it possible to deal with a general NDMT program, the running time of which is polynomial, and to obtain a general reducibility of the language recognized by this program to Lvyp. If this general reducibility is specialized for a specific NDMT program M that recognizes Lm, then the desired polynomial reduction of Lm will be obtained to Lissue Thus, essentially, for all L ε NP, a general proof will be presented that L ∞ Lout.

First, consider an arbitrary NDMT program M with polynomial running time, which has components Г, Σ, b, Q, q 0 , q y , q n , δ and recognizes the language L = L M . In addition, let p(n) be a polynomial with integer coefficients that bounds from above the time complexity T m (n). (Without loss of generality, we can assume that p(n) ≥ n for all n ε Z+.) The function f L implementing general reducibility will be described in terms of M, Г, Σ, b, Q, q 0, q Y, q n, δ and r.

It is convenient to think of f L as a mapping from the set of words in alphabet 2 to individual problems from the VEP, rather than to words in the alphabet S that encode problems from the VVP, since the details associated with the encoding can be easily filled in. Thus, the function f l will have the property that for all x ε Σ* membership x ε L takes place if and only if for the set of disjunctions f l (x) there is a satisfying set of truth values. The key to constructing a function f L is to use some set of disjunctions to write the statement that x is accepted by the NDMT program M, i.e. the statement x ε L.

If the input word x ε Σ* is accepted by program M, then for x there is a receiving computation of program M such that the number of steps in the verification stage and the number of symbols in the guess word are limited by p(n), where n = |x|. Only cells with numbers from -p(n) to p(n)+1 will participate in such a calculation. This follows from the fact that the read/write head starts working in cell number 1 and at each step moves no more than 1 cell. The verification calculation is completely determined by specifying at each moment of time the contents of cells with the specified numbers, the internal state and the position of the reading/writing head. Further, since there are no more than p(n) steps in the verification calculation, it is necessary to take into account no more than p(n)+1 time points. This allows such a computation to be completely described using a polynomially limited number of Boolean variables and a certain set of truth values ​​on their set.

The set of variables U involved in the description of the function f L is intended specifically for these purposes. Let us renumber the elements of the sets Q and Г as follows: Q: q 0, q 1 = q y, q 2 = q N, q s, ..., q r, where r = |Q|; G: s 0 = b, s 1 s 2, ..., s v, where v=|G| - 1. Three types of variables will be involved in further reasoning, each of which is given a certain meaning according to Fig. 2.7. In this case, the phrase “at time i” serves as an abbreviation for the exact expression “after performing the j-ro step of the verification calculation.”

The calculation of the program M obviously induces a set of truth values ​​on the set of these variables, if we accept the agreement that when the calculation ends before time p(n), the configuration remains unchanged at all times after stopping, i.e. the final state, the position of the head and recording on tape. At time zero, the tape entry consists of the input word x, located in cells numbered 1 to n, and the guess word w in cells numbered -1 to |w|, with all other cells empty.

On the other hand, an arbitrary set of truth values ​​for these variables does not necessarily correspond to any computation, much less the receiving one. Given an arbitrary set of truth values ​​for variables in a certain cell, they could

rice. 2.7. Disjunction Set Variablesfl(x) and the meaning attached to them

If several different characters were written simultaneously, the machine could be in several different states at the same time, and the read/write head could simultaneously view any subset of cells numbered from -p(n) to p(n)+1. The description of the function f L is carried out by constructing such a set of disjunctions containing the listed variables such that the set of truth values ​​will be fulfilling if and only if this set of truth values ​​is induced by some receiving calculation on the input x, and the stage of checking this calculation is performed in no more than p (n) steps and the guess word has a length of no more than p(n). Thus we get the implications:

x ε L ↔ at the input x there is a receiving calculation of the program M

↔ at the input x there is a receiving calculation of the program M, the number of steps of which does not exceed p(n), and the guess word w has a length equal to p(n).

↔ there is a task that performs the task of truth values ​​for a set of disjunctions of the problem f l (x).

This will mean that f l satisfies one of the two conditions required in the definition of polynomial reducibility. Another condition, that fl must be computable in polynomial time, can be easily verified once fl is described. will be finished.

The disjunctions of an individual problem f i (x) can be divided into 6 groups, each of which will impose a constraint of some type on any satisfying set of truth values. These groups are shown in Fig. 2.8.

Rice. 2.8.Groups of disjunctions forf L (x) and the restrictions they impose on the fulfilling set of truth values.

It is easy to see that if all 6 groups of disjunctions actually achieve their intended goals, then the executing set of truth values ​​must match the desired receiving computation on input x. The only thing that remains is to indicate a way to construct groups of disjunctions that realize these goals.

Group G 1 consists of the following disjunctions:

(Q, Q, .... Q(i, r]), 0

The first p(n)+1 of these disjunctions can be executed simultaneously if and only if at each moment of time i the program M is in at least one state. The remaining (p(n)+1) (r + 1) (r/2) disjunctions can be executed simultaneously if and only if at no time i the program M is in more than one state. Thus G1 fulfills its purpose.

The groups G 2 and G 3 are constructed similarly, but the groups G 4 and G 5 are very simple, each involving disjunctions consisting of only one literal. In Fig. 2.9 provides a complete description of the first five groups of disjunctions. Note that both the number of disjunctions in these groups and the maximum number of literals included in each disjunction are limited by a certain polynomial in n (since r and v are constants that are determined by M and, therefore, by the language L).

Rice. 2.9.The first 5 groups of disjunctions for f L (X).

The description of the last group of disjunctions is somewhat more complicated - G 6, which guarantees that each subsequent configuration of the machine is obtained from the previous one as a result of applying one command of the M program. This group consists of two subgroups of disjunctions.

The first subgroup guarantees that if the read/write head at time i is not looking at cell number j, then the character in cell number j from time i to time i + 1 will not change. The disjunctions of this subgroup have the form

Let us arbitrarily fix the moment of time t, the cell with number j and the symbol s l If at the moment of time i the reading/writing head is not looking at the cell with the number j and in this cell at the moment of time i the symbol j is written, and at the moment of time i + 1 it is already there no, then the above disjunction will not be satisfied (otherwise it will be satisfied). Thus, 2(p(n)+ l) 2 (v + 1) disjunctions of this group fulfill their purpose.

The second subgroup of disjunctions from group G 6 guarantees that the restructuring of one machine configuration into the next occurs according to the transition function δ of the program M. For each four

(i, j, k, l), 0 ≤ i< p(n), -р(n) ≤ j ≤ р(n) + 1, 0 ≤ k ≤ r и 0 ≤ l ≤ v,

this subgroup contains the following three disjunctions:

where the values ​​of ∆, k" and l" are defined as follows:

if q k ε Q\(q y , q N ), then δ(q k , s l) = (q k ` , s l ` , ∆),

and if q k ε (q Y , q N ), then ∆= 0, k" = k and l" = l.

It is not difficult to see (although it may take a few minutes of thought) that these 6(p(n))(p(n) + 1)(r+1)(v+1) disjunctions provide the necessary constraint on the fulfilling set of truth values.

Thus, we have shown how to construct groups of disjunctions G 1 -G 6 that fulfill their purpose. If x ε L, then the program M at the input x has a receiving calculation of length no more than p(n), and this calculation gives, for a given interpretation of the variables, a set of truth values ​​that will satisfy all disjunctions from C=G 1 UG 2 UG 3 UG 4 UG 5 UG 6 . Conversely, a set of disjunctions C is constructed such that anyone executing a set of truth values ​​for C must correspond to some receiving computation of the program M on input x. It follows that for f l (x) there is a satisfying set of truth values ​​if and only if x ε L.

Now it remains to show that for any fixed language L an individual problem f l (x) can be constructed in a time limited by a polynomial in n = |x|. If the language L is given, then you can choose some NDMT program M that recognizes L in a time limited by the polynomial p (there is no need to find the nondeterministic program itself in polynomial time, since it is only necessary to show that the mapping f l exists). If there is a certain NDMT program M and a polynomial p, then constructing a set of variables U and a set of disjunctions C requires a little more work than filling out all the positions in a standard (albeit rather complex) formula. The polynomial boundedness of this calculation will be clear if we show that Length is bounded above by a polynomial in n, where Length[I], as stated in Sect. 2.1, characterizes the length of the word encoding individual task I, under some reasonable encoding scheme.

As a “reasonable” length function for the VEP problem, we can, for example, take |U||С|. No disjunction can contain more than 2|U| literals (since the total number of literals is 2|U|), and the number of characters required to describe each individual literal is no more than log|U|, but this value can be neglected since it makes a polynomial contribution to the total length of the problem . Since r and v are fixed in advance, they can increase |U| and |C| a constant number of times, so we have |U| = O(p(n) 2) and |C| = O(p(n)) 2 . Therefore, Length = |U|| C| = O(р(n) 4) and, therefore, is limited by a polynomial in n, as required.

Thus, the transformation f l can be computed by an algorithm that has polynomial time complexity (however, the specific polynomial bound on the complexity will depend on L as well as the choice of M and p), from which we can conclude that for all L ε NP the function f L is computable in polynomial time and maps L into OUT (more precisely, maps L into Lout). This implies the assertion of the theorem that VYP is an NP-complete problem.▀

Proof of the results aboutN.P.- completeness

3-SATILIZABILITY (3-ISSUE)

CONDITION. Given a set C = (c 1 , c 2 , ..., c m ) of disjunctions on a finite set of variables U such that |c i | = 3, 1 ≤ i ≤ m.

QUESTION. Is there a set of truth values ​​on U such that all the disjunctions in C hold?

THREE-DIMENSIONAL COMBINATION (3-C)

CONDITION. Given a set M ε W x X x Y, where W, X and Y are disjoint sets containing the same number of elements q.

QUESTION. Is it true that M contains a three-dimensional combination, i.e., a subset M" ε M, such that |M`|=q and no two different elements of M" have any equal coordinates?

VERTICAL COATING (VP)

CONDITION. Given a graph G =(V, E) and a positive integer K, K ≤ |V|.

QUESTION. Does the graph G have a vertex cover of at most K elements, i.e., a subset V" ε V such that |V`| ≤ K and for each edge (u, v) ε E at least one of the vertices u or v belongs to V`?

CLIQUE

CONDITION. Given a graph G=(V, E) and a positive integer J ≤ |V|.

QUESTION. Is it true that G contains some clique of cardinality at least J, that is, a subset V` ε V such that |V`| ≥ J and any two vertices from V are connected by an edge from E?

HAMILTONIC CYCLE (HC)

CONDITION. Given a graph G=(V, E).

QUESTION. Is it true that G contains a Hamiltonian cycle, i.e. such a sequence vertices of the graph G such that n=|V|, (v n ,V 1) ε E and (v i , v i +1 )ε E for all i, 1≤ i ≤ n.

BREAKING

CONDITION. Given a finite set A and a “weight” s(a) ε Z+ for each a ε A.

QUESTION. Is there a subset A" ε A such that

3-feasibility

Problem 3-SATITIZABILITY is simply a restricted version of the SATISFACTION problem in which each individual problem has exactly three literals in each clause.) Because of its simple structure, this problem is most often used to prove NP-completeness results.

Theorem 3.1. Problem 3-SAITIZABILITY isN.P.- full.

Proof. It is easy to see that 3-OUT ε NP. This follows from the fact that a non-deterministic algorithm needs to guess only a set of truth values ​​of the problem variables and check in polynomial time whether, with such a set of truth values, all given triliteral disjunctions will be satisfied.

Let's reduce the problem VYP to the problem 3-VYP. Let U = (u 1 , u 2 , …, u n ) be a set of variables and C = (c 1 , c 2 , ..., c m ) be an arbitrary set of disjunctions that defines an arbitrary individual problem from VO. Let us construct a set C" of triliteral disjunctions on some set of variables U" such that C" is satisfied if and only if C is satisfied.

The set C" will be constructed by replacing each individual disjunction c j ε with an "equivalent" set C` j of triliteral disjunctions on the set U of original variables and the set U" j of some additional variables, and the variables from U" j will be used only in disjunctions from C` j... In other words,

Thus, you only need to show how, based on cj, you can construct C` j and U` j. Let c j be given by the set (z 1, z 2, ..., z k), where z i, are literals on the set U. The method of forming C` j and U" j depends on the value of k.

To prove that there is indeed reducibility here, it is necessary to show that the set of disjunctions C" is satisfied if and only if we satisfy the set of disjunctions C. Suppose first that t: → (T, F) is a set of truth values, executing C. Let us show that t can be extended to a set of truth values ​​t": U" → (T,P) that executes C". Since the variables in the set U"\U are divided into groups U` j and since the variables in each group U` j are included only in the disjunctions belonging to C` j, then it is enough to show how t can be extended to each set U` j separately , and in each case it is necessary to check that all disjunctions are satisfied in the corresponding set C` j .

This can be done as follows. If U` j are constructed, as in case 1 or 2, then the disjunctions from C` j are already performed by t, so t can be extended to U` j arbitrarily, for example, if we put t"(y) = T for all y ε U" j . If U" j is constructed as in case 3, then U` j is empty and the only disjunction in C` j is already satisfied by t. Only case 4 remains, which corresponds to the disjunction (z 1 , z 2 , ... .. ., z k ) from C, and k > 3. Since t is a fulfilling set of truth values ​​for C, then there is an integer l such that z l at t takes on the value true. If l = 1 or 2, then we set t"(y i j) =F, 1 ≤ i ≤ k - 3. If l = k - 1 or k, then we set t"(y i j) = F, 1 ≤ .i ≤ k - 3. Otherwise we set t"(y ij) = T for 1 ≤ i ≤ l -2 and t" (yij) = F for l-1 ≤ i ≤ k -3. It is easy to check that such a set of truth values ​​will ensure that all disjunctions in C`j are satisfied, so t` fulfills everything disjunctions from C". Conversely, if t" is some satisfying set of truth values ​​for C", then it is easy to check that the constraint t" on variables from U must be a satisfying set of truth values ​​for C. Thus, C" is satisfied if and only if we satisfy C .

In order to verify that this reducibility is polynomial, it is enough to note that the number of triliteral disjunctions in C" is limited by a polynomial in etc. Consequently, the size of an individual 3-VYP problem is limited from above by a certain polynomial from the size of the corresponding VYP problem, and since all the details constructions of reducibility are obvious, it will not be difficult for the reader to verify that this reducibility is polynomial.▀

The limited structure of the 3-RIN problem makes it much more useful in proving NP-completeness results compared to the RIN problem. Any proof based on the ER problem (except for the one just given) can be easily converted into a proof based on 3-ER, even without changing the function that performs the reducibility. In fact, the additional condition that all disjunctions have the same length can often simplify the reducibility to be constructed, and thus make it easier to find. Moreover, the very short length of disjunctions allows the use of reducibilities that could not be constructed at all for individual problems with disjunctions of greater length. This suggests that it would be even better if the analogous 2-SATIFIABILITY problem (each disjunction contains exactly two literals) could be shown to be NP-complete. However, 2-VYP can be solved by the “resolution” method in a time limited by a polynomial of the product of the number of disjunctions and the number of variables of a given individual problem (see also), and, therefore, belongs to the class P.

To do this, you just need to sit down, think and solve one of the mathematical “millennium problems”.

7X7

Since the last century, the number of such problems has decreased almost fourfold. When famous German mathematician David Gilbert at the very beginning of the 20th century, he spoke at the international mathematical congress in Paris; his list of mathematical and logical problems that needed to be solved in the next hundred years included 23 items. Plus three more problems with which the speech began, and which, having already been mentioned, were not included in the main list. They seemed so self-evident to Gilbert.

In total, by the end of the century, 20 problems had been completely solved. The first to be presented and the last to be solved was Fermat's Last Theorem. Two of the remaining problems were partially solved, two are still open, one - about the mathematical description of physical axioms - was recognized as non-mathematical, and one - about a straight line, as the shortest connection of two points - was declared too vague, which made it impossible to understand. whether it is resolved or not. What’s interesting: all 20 problems were solved completely free of charge. Solving Gilbert's problems did not imply any reward other than eternal scientific glory and deep scientific satisfaction.

The new list, compiled at the beginning of this century, of the world's mathematical problems numbered only seven. Unlike Gilbert's, the current list, called Millennium Prize Problems, is awarded for solving each of them. Clay Mathematics Institute(Cambridge, Massachusetts, USA) a prize of $1 million was awarded. Or rather, on the contrary: exactly seven problems were chosen according to the number of millions allocated for their solution.

Antithesis

The first Clay Million was awarded on March 18, 2010 43 year old Russian mathematician, employee of the St. Petersburg branch of the Steklov Mathematical Institute, Grigory Perelman, who solved the so-called “Poincare problem”.

It is believed that one of the reasons why this St. Petersburg mathematician, whom the British newspaper The Daily Telegraph ranked 9th in the list of one hundred living geniuses, refuses to communicate with Russian journalists is their blatant familiarity and incompetence. And it is true. Quite often in articles Grigory Yakovlevich is called not even Grigory, but Grisha, and his father is called the great popularizer of science. At the same time, the authors of the articles do not even bother to open the encyclopedia and find out that Yakov Isidorovich died of hunger in besieged Leningrad in 1942, and Grigory Yakovlevich was born only in 1966, 24 years later.

Even at school, the boy showed considerable abilities, not only in mathematics, but also in music. In addition to the usual, he also went to a music school, where he studied violin, and to the mathematics center at the Palace of Pioneers. Already in high school, he transferred to a specialized physics and mathematics school, from which he graduated with a silver medal. Poor physical preparation prevented him from getting a gold medal: no matter how hard he tried, the future mathematical genius was unable to pass the GTO standards.

After school, he, as a medalist, faced a difficult choice of where to go without exams - to the Conservatory or to the Mathematics and Mechanics of Leningrad State University. Passion for mathematics won out. He graduated from the university with honors. In 1990, Grigory Yakovlevich defended his PhD thesis and went to work in the USA, from where he returned six years later. At the same time, he was awarded the European Mathematical Society Prize for young mathematicians, but Grigory Yakovlevich refused to receive it. He worked as a leading researcher at the laboratory of mathematical physics at the St. Petersburg branch of the Mathematical Institute named after. V. A. Steklova RAS (POMI), but in 2005 he resigned and almost completely interrupted contacts with the outside world. And a year later, for solving one of the “Prize problems”, namely the “Poincaré problem”, he was awarded the main prize among mathematicians - the Fields Medal (cash equivalent - 15,000 Canadian dollars, at today's exchange rate - 432,000 rubles).

But Perelman also refused the Fields Medal. For two years, experts checked the correctness of his decision. And only in 2010, the academic council of the Clay Institute announced that no errors or fraud were found, and the Russian mathematician could come for money. However, Perelman announced that he was not going to fly to Cambridge. He also refused other options for transferring a million dollars. In one of his few interviews, he explained his action this way:

- I refused. You know, I had a lot of reasons in both directions. That's why it took me so long to decide. In short, the main reason is disagreement with the organized mathematical community. I don't like their decisions, I think they are unfair. I believe that the contribution of the American mathematician Hamilton to solving this problem is no less than mine.

And more recently, in another interview, Grigory Yakovlevich admitted:

“I have learned to calculate voids, and together with my colleagues we are learning the mechanisms for filling social and economic “voids.” There are voids everywhere. They can be calculated, and this gives great opportunities... I know how to control the Universe. And tell me - why should I run for a million?!

What's left

Anyway, one million is already gone. But there are still six left. What else can you get them for?

Birch and Swinerton-Dyer conjecture

The “philosopher's stone” of mathematics can be called equations of the form x n +y n +z n +.....=t n. The simplest thing, x 2 +y 2 =z 2 (for example, 3 2 +4 2 =5 2), was fully explored 300 years before the birth of Christ by Euclid. The most famous of these equations became the basis for Fermat's theorem. And one of the biggest solutions (in the pre-computer era) was proposed by Euler in 1769. He managed to construct the following equality: 2 682 4404 + 15 365 6394 + 18 796 7604 = 20 615 6734. There is no universal calculation method for such equations. However, it is known that each of them can have either a finite or an infinite number of solutions. Mathematicians Birch and Swinerton-Dyer in 1960 created a method by which each such equation can be reduced to a simpler one, called the zeta function. According to their experimentally derived but not theoretically proven assumption, if this function at point 1 is equal to 0, then the number of solutions to the desired equation will be infinite. Otherwise, they will either not exist at all, as is the case with Fermat’s theorem, or there will be some limited number of them. So far no one has been able to prove or disprove this statement.

Hodge conjecture

It is more difficult to study an object, the more complex its structure. Therefore, mathematicians usually first try to decompose it into simpler objects, which, as is clear, are easier to work with. The problem is that it is not always possible to simply decompose an object into its components. Sometimes, in this case, new parts appear, it is unknown where they came from and it is not clear what they represent. Or, on the contrary, a more detailed study reveals that some details are clearly missing. Simply put, by examining just bricks, we cannot imagine what a house made from them is like, what it looks like, and by what rules it is built. To do this, you need, at a minimum, to also study the empty space of the rooms enclosed between them. Cambridge professor William Hodge, in his writings in 1941, described the conditions under which, it seems to him, such incomprehensible “extra” parts cannot arise and in which any geometric body can be studied as an algebraic equation, creating its mathematical model. Scientists have been unable to prove his assumption or refute it for 70 years.

Navier-Stokes equations

When you are sailing on a lake on a boat, waves spread out from it. Following a flying plane or a speeding car, turbulent flows arise - wave-like air vortices. All these phenomena are described by the Navier-Stokes equations created back in 1822. Despite the fact that the equations have been created for quite a long time, no one still knows how to solve them. Moreover, no one even knows yet whether there is a way to solve them at all. At the same time, they are very actively used not only by mathematicians, but also by designers of aircraft, cars and ships. True, for now they can only be used using the NT method (“scientific poking”): substituting already known values ​​of speed, time, pressure, density, and so on, and checking whether they fit together. If someone finds a solution method, it will be possible to use the equations in the opposite direction, calculating all the necessary parameters from the equality. This will make aerodynamic testing unnecessary. However, the mathematician will receive a prize even if he proves that there is no solution method.

Decision-Check Problem (Cook-Lewin Problem)

If a person is given the task of finding a treasure buried there in the last century in the forest, he can spend a year, two, a decade, or even his whole life on the search. Everything happens much faster when they tell him: “The treasure is buried under the only aspen tree in the forest. Go and check." The same thing happens when solving any problem. We all understand perfectly well that checking a solution usually takes less time than the solution itself. We understand, but as it turns out, we cannot prove this simple and seemingly logical fact. And therefore, if you manage to find such a problem, checking the correctness of the solution of which, regardless of the verification method, will take more time than the solution itself - urgently contact the Clay Institute, and in two years you will become the owner of a million dollars. The solution to the “Cook problem” formulated in 1971, according to scientists, will lead to a real revolution in the field of cryptography and to the emergence of encryption systems that simply cannot be cracked. Very rudely: ciphers will appear, the verification of the correctness of breaking which will take an infinitely long time.

Riemann hypothesis

Among the whole mass of numbers, a special place is occupied by numbers that cannot be divided into anything smaller than themselves: 1, 2, 3, 5, 7, 11, 13, 17 and so on. Such numbers are called “prime” and they are extremely important for mathematicians. How they are distributed along the numerical series is only known to God. Riemann in 1859 did not even propose a way to find or test them. The only way to check whether a number is “prime” or not is to try to divide it into smaller and smaller numbers (the largest “prime” known to date was found in August 2008 and consists of 12,978,189 digits). He simply found a method by which one can determine the maximum number of prime numbers that do not exceed a certain given number. To date, mathematicians have tested this method with one and a half trillion “simples”. No glitches have been found so far. However, this does not mean at all that the method will not stumble on the first one and a half trillion check. And, since the Riemann hypothesis, which was transferred to the new list from the Gilbert list, is actively used to calculate data transmission security systems - in cellular networks, on the Internet, and so on - its proof has a very practical meaning. And there is something to pay here for a million.

Yang-Mills equations

American physicists Zhen-Ning Yang and Robert Mills compiled their quantum equations in 1954, observing the movement of elementary particles. Derived almost from pure intuition, they nevertheless remarkably describe almost all types of their interactions. Using the equations, the discovery of new particles was even predicted, which were later actually found by nuclear physicists at the world's largest laboratories - Brookhaven, Stanford and CERN. True, using the Yang-Mills theory it is impossible to correctly predict the mass of particles, however, despite this, almost all nuclear scientists in the world confidently use the equations. Although it is still unclear how they work and, in general, whether they are so true. Of all the above equations, these are the most complex, so we will not present them. But, if the five million that you can get for solving the previous five problems is not enough for you, no one will stop you from trying to solve this one as well. Dare - and you will find it.

Or maybe we should wait?

Perelman's surname is now remembered by the entire civilized world. But who is this Andrew Wiles Only experts know. But in 1995, it was he who fulfilled the centuries-old dream of mathematicians - he proved Fermat’s Last Theorem, formulated back in 1637. For its solution in 1908, a special prize of 100,000 German marks was also announced, which was extremely high for the beginning of the last century. However, two world wars and the associated inflation cut it down quite significantly. So much so that the mathematician received a purely symbolic amount for his work, approximately equivalent to 15 dollars. If Wiles had waited 6-7 years to publish his proof, Fermat’s theorem would have definitely been included in the “Millennium Prize Problems” and would have been valued at a million. And then the mathematician would become very rich. Or very famous. Like Grigory Perelman.