Min-plus polynomials, cyclic games, and Hilbert's theorem on zeros
This paper discusses algorithmic problems associated with min-plus polynomials. More specifically, the solvability of systems of linear min-plus polynomials. This task turns out to be polynomially equivalent to the problem of determining the winner in the so-called cyclical games (mean payoff games), a well-known problem that lies in the intersection of the complexity classes NP and coNP. The second result, which is discussed in the course of the report, is an analogue of Hilbert's theorem on zeros for min plus algebra.
A min-plus (or tropical) semiring is a set of rational numbers with two operations: a min-plus addition, which is just the operation of taking the minimum, and a min-plus multiplication, which is the usual addition. The polynomials over the min-plus semiring are determined by analogy with the classical polynomials. Essentially, the min-plus polynomial sets a piecewise linear function of its variables. The root of a polynomial is the point of non-smoothness of this function.
')
The report was read at the Faculty of Computer Science, opened at HSE with the support of Yandex. Lecturer Vladimir Podolsky - Senior Researcher, Mathematical Institute. V.A. Steklov. At the NFC, he lectures and conducts seminars within the framework of the Discrete Mathematics course. The report is based on collaborations with Dmitry Grigoriev .
Under the cut - a full transcript of the lecture.
What is a min-plus half ring (or tropical ring)? We have a set, there are two binary operations, the set is not arbitrary, but quite specific (for example, real, rational, integer numbers, etc., and all can be considered the same with the addition of positive infinity). The role of addition in this min-plus ring is played by an ordinary operation of a minimum, and the role of multiplication is an ordinary operation of addition. A fairly simple structure: it is a group by multiplication, and by addition is a semiring (there are no inverse elements). And the addition of infinity has the meaning of zero in min-plus addition.
We will consider polynomials in this algebraic structure. They are defined by analogy with ordinary polynomials, that is, you can define monomials by min-plus multiplication (on the right are written in ordinary terms, that is, a monomial is just a linear function with integer coefficients, in other words, both 1 and n are integers). We will designate them as written on the slide.
A polynomial is simply the sum of several monomials. In conventional terms, this is the minimum of each M i .
The degree of a monomial is determined in a natural way - the sum of the degrees of all variables entering here. The power polynomial is the degree of maximal monomial in it.
What becomes unusual here in comparison with classical polynomials is the definition of the concept of the root of a polynomial. Point A is a root if, when it is substituted into this expression, the minimum is reached on at least two different monomials (or is equal to infinity).
Consider an example. (Multiplication by zero in this case makes sense, because the multiplication sign here is actually an addition.) Let's try to understand what this polynomial roots are. We need the minimum to be achieved on two different monomials. You can pick and understand that the roots are -2 and 1.
Consider another example. There are already three variables, and the polynomial is actually linear. On the left it is written in min-plus terms, on the right - in ordinary terms. The polynomial is linear, that is, each monomial in it is linear, it already has more roots. It should be noted that there is such a special root (-1, -2, 1) in which all three monomials coincide. And from it you can already make a lot of others, namely if you add something to any coordinate, then it is clear that it will still remain the root. Well, it is also useful to note that in this case, if we have some kind of root and we add the same number to all coordinates, it will still be the root.
Along with such tropical polynomials, one can consider min-plus polynomials. This is such an equality: on the left and on the right there are sums of monomials, and it is powerfully defined in the same way, and the root is determined in the most usual way. Point A is a root if the left and right sides are equal. This method is justified by the fact that there is no subtraction in the min-plus ring, so it is reasonable to look at the equality of the polynomial zero as bilateral equality, where part of the monomials is on the left, part of the monomials is on the right.
Where does all this basically come from? The min-plus variant of polynomials usually arises from combinatorial optimization problems and from scheduling theory problems. Consider some weighted graph, that is, one that has weights on the edges. Take its adjacency matrix and, let's say, in a min-plus sense, we square it. Then you can think a little and understand that the length of the shortest path of length 2 between these two vertices will be written in the cell of such a matrix. When we build this matrix in a min-plus sense in a square, then we take a row and a column, multiply the cells in a min-plus sense, that is, add, then take the minimum. The length of the shortest path and occurs, length 2. If you take a large degree, then there are shortest paths of greater length. In principle, the min-plus polynomial looks more natural. In fact, it is probably more difficult to understand how such a strange formulation is obtained, when we have a polynomial and we want the minimum to be achieved in two monomials. Such a formulation occurs in problems of algebraic geometry and other branches of mathematics.
How can such a thing arise? Let's look at rational functions over complex numbers. And let's close this field algebraically. In the neighborhood of zero, such functions can be represented by Puiseux series — by such infinite series. The degrees here are rational, and the coefficients too.
d 1 is the smallest degree and is called the order of such a series. Now over this field we consider some polynomial in n variables. Let us try to understand what may mean in general that some point in this field of rational functions is the root of such a polynomial in many variables. This means that if we substitute it there, it will be 0. Let's see what happens when we substitute the whole thing in monomial: orders are added. When we multiply such series, the orders will be added. Then we add monomials. If we want to end up with 0, it is necessary that the monomial of the minimal order be reduced with something. This means that there must be at least two of them - the minimum order must occur from at least two different monomials. Something like this usually occurs. If we consider such polynomials and look at their orders and similar polynomials for their orders, then it turns out that if we have a root, then the orders of these a1, an must satisfy a similar tropical polynomial.
The classical application of the science of tropical polynomials is the problem of calculating plane algebraic curves.
Suppose we have algebraic curves over complex numbers. Then if we fix a certain number of points and say: let an algebraic curve pass through them, then there will be not so many such algebraic curves, some finite number. For example, if we are talking about curves of degree 1, then these are simply straight lines, and if we fix two points in one position, then such a straight line will be exactly one.
In the general case, consider curves of degree d. In fact, they are still considering curves that have double points, that is, points that they pass through several times. Fix also something with a number of double points. Next, we fix a certain number of points C on the plane in general position. And if you choose C correctly, then it turns out that the number of curves that pass through these points of a given degree and with a given number of double points will be equal to some non-zero constant. If you take C too small, then there will be infinity; if you take too big, then zero.
Consider an example. Curves of degree 2 and with one double point. Curves of degree 2 are ellipses, parabolas, hyperbolas. How can such a curve of degree 2 have a double point? So, this is the intersection of two straight lines. How many parameters are there? There are six formal coefficients, but all of them can be multiplied by one constant, in fact, there are five degrees of freedom. The fact that there is a double point reduces this all by one, four degrees of freedom remain. If we take four points in general position, then how many ways can we draw a pair of intersecting straight lines through them? If we take a quadrilateral, then there will be three such pairs of intersecting straight lines.
There is a task to find what this number is equal to, and it is solved by passing to such tropical polynomials.
Solution plan: it is useful to prove that the number m we are looking for, that is, the number of such curves, does not depend on the points.
Then you can take points of this type (the point is complex, t is a real number, x /, y / is also real, the whole complexity sits in φ and ψ). And after that t rush to infinity. Just as it was on the pair of previous slides, it turns out that a tropical polynomial arises from the variables x /, y /, and if you understand how many solutions it has, then we get the number of such curves. The solution of a tropical polynomial is simpler than the solution of the original problem, because tropical polynomials are simple, you can draw something there, this is more of a combinatorial problem, it can be done algorithmically as well.
Let's call this tropical linear polynomial expression. In ordinary terms, this is the minimum. Here, in comparison with the general case, every variable must necessarily enter. If there is no infinity, then it essentially enters. Again, it is also still homogeneous. We are interested in the root, which is not infinity. Similarly, we can consider linear min-plus polynomial. The most common question for ordinary polynomials is the question of the solvability of linear systems.
We will consider systems of such polynomials. For min plus polynomials too.
You can look at the problem of solvability. A system of polynomials is given, and one wants to understand from it whether it is solvable or not. In the classical case, this problem is polynomially solvable, and it turns out that here the polynomial algorithm is unknown. We know that it lies in both the NP class and the coNP class.
There is a task for which there are answers “yes” and “no”, in our case - the problem of solvability. The problem lies in the NP class, if for each given input there is a short proof, by which it is possible to verify in polynomial time that the answer of the problem is “yes”. The task lies in the coNP, if the same is for the answer “no”.
We would like the problem to lie in P, that is, the system could immediately tell whether it is solvable or not. But instead, we know something else: if we were given such a system, then we know that we can come up with such a short proof that it exists, which can be checked in polynomial time. Proof that the system is either solvable or insoluble.
Slide number 13
A collection of tasks that lie on NP crossed with coNP. Some of them are also in R.
It turns out that in fact some of these tasks are one and the same task. That is, they are equivalent to each other.
The games were introduced in 1979 and 1988. The game is organized like this: we have two players, Alice and Bob, and they move some kind of chip along a bichromatic graph. Numbers are written in the bipartite graph on the edges. Alice's goal is to maximize the sum of the numbers on the edges along which the chip passes. Bob tries to minimize it. A specific game is a sequence of vertices that this chip has visited. The value of the game is the averaged number on the edge - that is, we take t steps, add up all the numbers that were on the edges along which we passed, divide by t. Next we take the limit. In this particular game, you can see how profitable it is for players to play and who exactly wins. What happens if Alice goes up? Bob will immediately return the chip back, that is, the total will be 1, Bob is profitable, so Alice has no special meaning to do so. Following the two moves, she returns to the starting position while losing 1. Therefore, let's see what happens with the other version. She went to 0, Bob now has options left and left and down. If he goes left and down, then Alice will have one move, the only one, and she can only go back, and according to the results of these two moves, Bob would lose two. It is unprofitable for him, so you should not do that.
We'll see what happens if it goes strictly to the left. Then Alice had the only move, again they returned to the same point, again Alice acquired 1. Thus, in any case, Alice still wins here. She needs to go here first (2), and then respond with her only moves, and every four moves she will win by 1. This is the best case for Bob, but she will accumulate the win all the same.
Alice wins if the value of the game is positive, and Bob does the opposite. It is known that one of the players always has a winning strategy. And it is also known that there is a positional winning strategy, which is intuitively obvious in general. Positional strategy is when a player's move depends only on where the chip is now. It is pretty obvious that the move should not depend on how they used to go.
So these games are defined. The problem with them is to understand who is winning (or rather, even to understand whether Alice wins, so that the answer is “yes”). This problem is in NP, because if Alice’s winning strategy is given as a certificate, it’s actually easy to check whether this strategy is really a winning one. The same task lies in the coNP, because the certificate that Bob is not losing is his strategy. If you give Bob a strategy, you can check in polynomial time that, no matter how Alice plays, she cannot win.
Now consider a slightly larger problem than the solvability problem. Also look at two more tasks.
Task: a matrix is given and a number is given, it is necessary to understand whether it is true that the dimension is not less than this number.
All these tasks are considered not only on Z, one can consider them on Z with the addition of infinity. And all of them are polynomially solvable in the classical case.
And in the tropical case, it turns out that no. The table contains all the results. There is a tropical case, there is a min-plus case, three problems are about solvability, equivalence, and dimension. It turns out that the dimension problem in the tropical case is simply NP-complete. There are different links. When there are two references, it means that in the first paper this result is proved over Z, and in the second, over Z∞. There is a significant difference - if there is infinity, then it is less pleasant and much more difficult to prove. Thus, in particular, it turns out that all these problems are equivalent to each other and it does not matter which one of them tries to prove that it lies in P.
How can you look at this picture? There is such an old task - Mean Payoff Games. And it is not yet resolved. We prove that there are quite new tasks that are equivalent to it. Some of them are formulated in certain algebraic terms, in some algebraic structure. Here is the problem of solvability of systems of tropical linear equations. Quite a task like that in a certain algebraic structure, we thus reformulated the task and cyclical games in such new terms. And one can hope that it will be possible to develop the science of tropical polynomials, and when it develops, it will turn out that there we will learn to prove that linear systems can be solved in polynomial time.
What is generally known in the algebraic theory about tropical polynomials? In the linear case, something is known.
There are various analogs of the rank of matrices in tropical algebra. There are actually quite a few of them, they have different meanings, there are different inequalities between them, but nevertheless something is learned there and something is known. There is an analogue of the determinant of the matrix, and it also has good properties there, it is also connected somehow with linear systems.
There is an analogue of the Gaussian triangular matrix.
In the general case, for arbitrary polynomials, much less is known. There is some work on the study of the radical, but especially no progress is visible. The problem of solvability is NP-complete. The system of polynomials is arbitrary, with no restrictions on degrees. In fact, polynomials in degree 2. If we have a system of tropical polynomials in degree 2, then the problem of its solvability is NP-complete.
In the classic case, the problem is already unsolvable.
What is proposed to do? In classical algebra there is a very important result of Hilbert's theorem on zeros.
We will tell about the analogue of this theorem in the tropical case. Here is the weak form of Hilbert's theorem on zeros. This theorem says this: let us have a system of classical polynomials, and we would like to understand that it has no solution. This theorem says that it means constructively that the system of polynomials has no solutions. It turns out that the system of polynomials does not have a general solution if there is their algebraic combination, which is identically 1. That is, simply the polynomial constant 1 is expressed as an algebraic combination of ours. And there is such a result that the system of polynomials does not have a solution if and only if there is such an algebraic combination. In the effective version, it is possible to estimate the degrees of these polynomials g 1 , g k , it can be said that the greatest degree of these products here is no more than 2 dmin (n, k) .
If you try to simply naively formulate an analogue of tropical polynomials, then nothing happens. For the same reason that there is no subtraction. Even if we write just two such polynomials, they have no common roots. No matter how hard we try, whatever algebraic combination we take, zero or one, we will not get it anyway, because this X will not be reduced with anything. Just not provided for such a possibility.
To formulate an analogue of Hilbert's theorem on zeros, we will have to reformulate a little the classical version itself.
To do this, we will have to consider such a Macauley matrix. Let's look at the polynomial system and just such a matrix. N is some parameter number. Its columns are labeled with monomials, the degree is not greater than N, the lines are labeled with polynomials from our system multiplied by monomials. And also degrees are not greater than N. The monomial coefficient in this polynomial is written in the cell of the matrix.
Example: f 1 = 1 + x, f 2 = 2 + y, N = 2.
Such lines are obtained, that is, we can multiply each of these polynomials by some of the variables.
This is actually a generalization of the Sylvester matrix to an arbitrary system of polynomials.
We formulate Hilbert's theorem on zeros in dual form. On the slide - first in the ordinary, and then in the dual. We have a system of polynomials, variables n, degree d. And it turns out that it has a common root if and only if there is a solution to such a linear system.
In principle, it is not difficult to understand. Here it says: we took the polynomials f i , multiply them into different monomials, then put them together. You can look at a polynomial as a vector of its coefficients. When we multiply f i by monomials, we get different lines of the Macauley matrix. And when we fold them, we take a linear combination of the lines of the Macauley matrix. And we want to eventually get a unit. That is, the fact that this system has a solution means that there is no linear combination of rows of the Macauley matrix, which is equal to the vector (1.0, ...). This means that the vector (1,0, ...) does not lie in the linear span of the lines of our matrix. So, we can choose a vector that will be orthogonal to all the lines of our matrix and will not be orthogonal to the vector (1,0, ...).
We define the Macauley matrix in the tropical version. It is defined in the same way: we have a system of polynomials, in the same way the columns are numbered by monomials, in the same way the lines are numbered by polynomials multiplied by monomials, and the same is written in the cells. When there is no monom, the role of zero is played by infinity. We are interested in a tropical linear system with a Macauley matrix. At the same time, we will be interested in such solutions so that 1 does not have 0, that is, not infinity.
We can formulate an analogue of Hilbert's theorem on zeros in dual form for tropical polynomials. Here the wording is exactly the same: the system has a solution if and only if the linear system with the Macauley matrix has a solution. Also, the theorem was proved when the variable is one. The general case is formulated as a hypothesis.
The theorem that this is actually true. Let's consider the system of tropical polynomials, by di we denote their degrees, by - the maximum degree. It turns out that the system has a solution if and only if the Macauley matrix also has a solution. As N you can take this.
In the case when we have no infinity, N is such a thing, it can be estimated as N multiplied by d multiplied by k.
When there is infinity, this is a more complicated thing - it is a polynomial in n, k (see slide). Both of these estimates are to some extent accurate. In fact, this is one of those rare examples when it turns out that it is essentially important whether infinity is there or not.
There is an analogue of this theorem for the min-plus case. The Macauley matrix can be defined in the same way for mine-plus cases, now there will be two of them, and we will already be interested in such a system, a two-sided, mine-plus linear system.
Similarly, we can formulate an analogue of Hilbert's theorem on zeros in the dual form: the min-plus system of polynomials has a solution if and only if such a linear system with Macauley matrices (as n must be taken the same as before).
Initially, this theorem was of dual form - that is, if something does not have a solution, then it has something else. Here this theorem does not have this form. They say that if there is a solution, then there is a solution. If there is no solution, then there is not. This is still not a dual result.
The result of the dual form can also be obtained, and it looks like this. There is a min-plus polynomial system, denoted degrees d. We can say that a system has a solution if and only if it is possible to assemble such a tropical algebraic combination of our polynomials such that for every monomial the coefficient on the left will be greater than the coefficient on the right.
Let there be a system of tropical polynomials. And tropical monomials too. Consider the algebraic combination of g. It is structured as follows: we multiplied the polynomials from f by monomials, and then all this is added. And such an algebraic combination is called nondegenerate if the following occurs:
Example. Consider two such polynomials. And we add them up with such coefficients. These are monomials of zero degree, but they are still monomials. Fold, get this expression. And you can see that the constant monom in the left side has a coefficient of 0, the coefficient in the right side is ½, in the left side it is less, and this is such a place where it is less. In the case of a monomial of degree 1, the coefficient ½ is on the right, the coefficient is on the left. Now it is smaller on the right, and this is the only place where it is smaller. That is, these two monomials are at least in different places. Thus, for these polynomials we can construct a non-degenerate algebraic combination.
It turns out that the existence of such a non-degenerate algebraic combination is the criterion that the system has no solution. In the presence of infinity it is not enough that there is just a nondegenerate algebraic combination, it is also necessary that the constant monomial be finite. Otherwise, there will be a solution in this algebraic combination.
This definition of a non-degenerate algebraic combination, although complicated, is testable.
How are the tropical and min-plus polynomials related? It turns out that in one direction they are connected very simply: if we have a system of tropical polynomials, then it is always possible to construct a system of mines-plus polynomials with the same variables and with the same set of solutions. In the opposite direction there is no such simple information. But it still is: if we have a min-plus system of polynomials, then we can build another tropical polynomial system, which will have twice as many variables, and we can embed the linear space Qn in the linear space Q2n so that all solutions f embeds exactly in all solutions t.
That is, the set of solutions of the system f was a kind of subset in the n-dimensional space, and in t the set of solutions is some kind of subset in the 2n-dimensional space. Nevertheless, one can simply put some solutions biologically into others, they simply correspond to each other.
These two correspondences make it possible to quickly move from the min-plus polynomials to the tropical polynomials. In the results that were listed, as soon as the theorem was proved for one case, it can be immediately translated for the second type of polynomials.
How does the proof of the last series of results work? First there is the tropical theorem on zeros in dual form. It is proved geometrically there. All the main content of the second part actually sits in this theorem. From it it is not very difficult to go to the min-plus case and get just such a theorem.
How is the transition to the theorem out of dual form? In fact, here one can use linear duality for tropical linear systems. It turns out that for them it is also possible to write out linear duality in a simple and understandable form and, having obtained the result, use duality for this linear system (No. 39), interpret the dual system in terms of algebraic combinations, and this will turn out (No. 40). Then from this theorem it is possible, again with the help of the system from the min-plus systems to tropical systems, to obtain (No. 43) the tropical system outside the dual form.
The idea of a geometric proof of the dual form theorem. A system of polynomials on Q has a solution if and only if there is a solution to such a linear tropical system. And in one direction it is simple: if the polynomial system has a solution, then the tropical linear system will also have a solution. It is necessary to remember that the columns Cn of the Macauley matrix correspond to monomials in the variables X. And if there is any solution for the system of polynomials X, we must set i to be equal to this monomial, then in the rows of the Macauley matrix we simply have the coefficients of the polynomial f multiplied by monom. And since X was a solution to the polynomial f, then y will be a solution to the linear equations defined by these lines of the Macauley matrix.
In the other direction is more difficult. It is necessary to do the following: we know that there is some solution to this system, that is, there is some vector Y. We would like to make from it a vector that will have such a form, that is, how it will come from some X.
Firstly, it is useful to fix N = 2, this is the entire substantial case: as soon as it is proved for two, for large n it is generalized instantaneously. We regularly have vectors whose coordinates are numbered by pairs of non-negative integers. For example, these are polynomial coefficients. In fact, they are numbered monomials. The lines of the matrix Macauley and its solution in the same way.
You can look at all these vectors, at all these objects as a set of points in three-dimensional space. The first two coordinates we correspond to the coordinates of the vectors, and the third coordinate corresponds to the values of these coordinates. Then we have polynomials f i from f will correspond to the set of points P fi - this is the set corresponding to their coefficients. . Macauley - . , P fi . Macauley - . .
, Macauley, , , . –. +Y i -Yi. , . P y , Y, , . Y – . ? , Py , . , . , P y , , , . , Y .
, Y , – . , , . - , . , . Y, . .
P fi , , . , .
Y , . : P fi , , – Macauley. Y, , . , , . .
A min-plus (or tropical) semiring is a set of rational numbers with two operations: a min-plus addition, which is just the operation of taking the minimum, and a min-plus multiplication, which is the usual addition. The polynomials over the min-plus semiring are determined by analogy with the classical polynomials. Essentially, the min-plus polynomial sets a piecewise linear function of its variables. The root of a polynomial is the point of non-smoothness of this function.
')
The report was read at the Faculty of Computer Science, opened at HSE with the support of Yandex. Lecturer Vladimir Podolsky - Senior Researcher, Mathematical Institute. V.A. Steklov. At the NFC, he lectures and conducts seminars within the framework of the Discrete Mathematics course. The report is based on collaborations with Dmitry Grigoriev .
Under the cut - a full transcript of the lecture.
What is a min-plus half ring (or tropical ring)? We have a set, there are two binary operations, the set is not arbitrary, but quite specific (for example, real, rational, integer numbers, etc., and all can be considered the same with the addition of positive infinity). The role of addition in this min-plus ring is played by an ordinary operation of a minimum, and the role of multiplication is an ordinary operation of addition. A fairly simple structure: it is a group by multiplication, and by addition is a semiring (there are no inverse elements). And the addition of infinity has the meaning of zero in min-plus addition.
We will consider polynomials in this algebraic structure. They are defined by analogy with ordinary polynomials, that is, you can define monomials by min-plus multiplication (on the right are written in ordinary terms, that is, a monomial is just a linear function with integer coefficients, in other words, both 1 and n are integers). We will designate them as written on the slide.
A polynomial is simply the sum of several monomials. In conventional terms, this is the minimum of each M i .
The degree of a monomial is determined in a natural way - the sum of the degrees of all variables entering here. The power polynomial is the degree of maximal monomial in it.
What becomes unusual here in comparison with classical polynomials is the definition of the concept of the root of a polynomial. Point A is a root if, when it is substituted into this expression, the minimum is reached on at least two different monomials (or is equal to infinity).
Consider an example. (Multiplication by zero in this case makes sense, because the multiplication sign here is actually an addition.) Let's try to understand what this polynomial roots are. We need the minimum to be achieved on two different monomials. You can pick and understand that the roots are -2 and 1.
Consider another example. There are already three variables, and the polynomial is actually linear. On the left it is written in min-plus terms, on the right - in ordinary terms. The polynomial is linear, that is, each monomial in it is linear, it already has more roots. It should be noted that there is such a special root (-1, -2, 1) in which all three monomials coincide. And from it you can already make a lot of others, namely if you add something to any coordinate, then it is clear that it will still remain the root. Well, it is also useful to note that in this case, if we have some kind of root and we add the same number to all coordinates, it will still be the root.
Along with such tropical polynomials, one can consider min-plus polynomials. This is such an equality: on the left and on the right there are sums of monomials, and it is powerfully defined in the same way, and the root is determined in the most usual way. Point A is a root if the left and right sides are equal. This method is justified by the fact that there is no subtraction in the min-plus ring, so it is reasonable to look at the equality of the polynomial zero as bilateral equality, where part of the monomials is on the left, part of the monomials is on the right.
Where does all this basically come from? The min-plus variant of polynomials usually arises from combinatorial optimization problems and from scheduling theory problems. Consider some weighted graph, that is, one that has weights on the edges. Take its adjacency matrix and, let's say, in a min-plus sense, we square it. Then you can think a little and understand that the length of the shortest path of length 2 between these two vertices will be written in the cell of such a matrix. When we build this matrix in a min-plus sense in a square, then we take a row and a column, multiply the cells in a min-plus sense, that is, add, then take the minimum. The length of the shortest path and occurs, length 2. If you take a large degree, then there are shortest paths of greater length. In principle, the min-plus polynomial looks more natural. In fact, it is probably more difficult to understand how such a strange formulation is obtained, when we have a polynomial and we want the minimum to be achieved in two monomials. Such a formulation occurs in problems of algebraic geometry and other branches of mathematics.
How can such a thing arise? Let's look at rational functions over complex numbers. And let's close this field algebraically. In the neighborhood of zero, such functions can be represented by Puiseux series — by such infinite series. The degrees here are rational, and the coefficients too.
d 1 is the smallest degree and is called the order of such a series. Now over this field we consider some polynomial in n variables. Let us try to understand what may mean in general that some point in this field of rational functions is the root of such a polynomial in many variables. This means that if we substitute it there, it will be 0. Let's see what happens when we substitute the whole thing in monomial: orders are added. When we multiply such series, the orders will be added. Then we add monomials. If we want to end up with 0, it is necessary that the monomial of the minimal order be reduced with something. This means that there must be at least two of them - the minimum order must occur from at least two different monomials. Something like this usually occurs. If we consider such polynomials and look at their orders and similar polynomials for their orders, then it turns out that if we have a root, then the orders of these a1, an must satisfy a similar tropical polynomial.
The classical application of the science of tropical polynomials is the problem of calculating plane algebraic curves.
Suppose we have algebraic curves over complex numbers. Then if we fix a certain number of points and say: let an algebraic curve pass through them, then there will be not so many such algebraic curves, some finite number. For example, if we are talking about curves of degree 1, then these are simply straight lines, and if we fix two points in one position, then such a straight line will be exactly one.
In the general case, consider curves of degree d. In fact, they are still considering curves that have double points, that is, points that they pass through several times. Fix also something with a number of double points. Next, we fix a certain number of points C on the plane in general position. And if you choose C correctly, then it turns out that the number of curves that pass through these points of a given degree and with a given number of double points will be equal to some non-zero constant. If you take C too small, then there will be infinity; if you take too big, then zero.
Consider an example. Curves of degree 2 and with one double point. Curves of degree 2 are ellipses, parabolas, hyperbolas. How can such a curve of degree 2 have a double point? So, this is the intersection of two straight lines. How many parameters are there? There are six formal coefficients, but all of them can be multiplied by one constant, in fact, there are five degrees of freedom. The fact that there is a double point reduces this all by one, four degrees of freedom remain. If we take four points in general position, then how many ways can we draw a pair of intersecting straight lines through them? If we take a quadrilateral, then there will be three such pairs of intersecting straight lines.
There is a task to find what this number is equal to, and it is solved by passing to such tropical polynomials.
Solution plan: it is useful to prove that the number m we are looking for, that is, the number of such curves, does not depend on the points.
Then you can take points of this type (the point is complex, t is a real number, x /, y / is also real, the whole complexity sits in φ and ψ). And after that t rush to infinity. Just as it was on the pair of previous slides, it turns out that a tropical polynomial arises from the variables x /, y /, and if you understand how many solutions it has, then we get the number of such curves. The solution of a tropical polynomial is simpler than the solution of the original problem, because tropical polynomials are simple, you can draw something there, this is more of a combinatorial problem, it can be done algorithmically as well.
Let's call this tropical linear polynomial expression. In ordinary terms, this is the minimum. Here, in comparison with the general case, every variable must necessarily enter. If there is no infinity, then it essentially enters. Again, it is also still homogeneous. We are interested in the root, which is not infinity. Similarly, we can consider linear min-plus polynomial. The most common question for ordinary polynomials is the question of the solvability of linear systems.
We will consider systems of such polynomials. For min plus polynomials too.
You can look at the problem of solvability. A system of polynomials is given, and one wants to understand from it whether it is solvable or not. In the classical case, this problem is polynomially solvable, and it turns out that here the polynomial algorithm is unknown. We know that it lies in both the NP class and the coNP class.
There is a task for which there are answers “yes” and “no”, in our case - the problem of solvability. The problem lies in the NP class, if for each given input there is a short proof, by which it is possible to verify in polynomial time that the answer of the problem is “yes”. The task lies in the coNP, if the same is for the answer “no”.
We would like the problem to lie in P, that is, the system could immediately tell whether it is solvable or not. But instead, we know something else: if we were given such a system, then we know that we can come up with such a short proof that it exists, which can be checked in polynomial time. Proof that the system is either solvable or insoluble.
Slide number 13
A collection of tasks that lie on NP crossed with coNP. Some of them are also in R.
- The problem of linear programming: we are given a system of ordinary linear inequalities, and we are interested in whether there is a solution. The task lies in NP. A simple proof that there is a solution is the decision itself. We can simply be given a solution, and we can easily substitute and check in polynomial time that this is indeed a solution, which means that the system is solvable. The task in this case lies in the coNP - this can be understood from duality. For a linear system there is a dual one: the first system has a solution only when the second one does not have it. Therefore, in order to prove that the system has no solution, it is necessary to present a solution for the dual.
- The problem of checking the number for simplicity: given a simple number, and we want to understand whether it is simple. Also located in coNP, it has long been known that it is in NP, crossed with coNP. Here it is easy to present proof that the number is not simple, it is enough to simply show its factorization, well, or just two factors. It is more difficult to explain how to prove that a given number is simple, to prove so that it can be checked.
- There is a series of tasks that are formulated as games. Challenges are who wins. Lies in NP crossed with coNP.
- There is a problem about checking the quadraticity of the deduction. That is, a number is given, a modulo of this number is given, and it must be understood whether it is quadratic or not. Lies in NP crossed with coNP.
- The problem of the approximation of the shortest vector in an integer lattice: an integer lattice with a basis is given, and we need to find the shortest vector in it. If we are not interested in the shortest vector itself, but in approaching it with the necessary parameters, then the problem also falls into NP intersected with coNP.
- The problem of solvability of min-plus linear systems.
- And the problem of solvability of tropical linear systems.
It turns out that in fact some of these tasks are one and the same task. That is, they are equivalent to each other.
The games were introduced in 1979 and 1988. The game is organized like this: we have two players, Alice and Bob, and they move some kind of chip along a bichromatic graph. Numbers are written in the bipartite graph on the edges. Alice's goal is to maximize the sum of the numbers on the edges along which the chip passes. Bob tries to minimize it. A specific game is a sequence of vertices that this chip has visited. The value of the game is the averaged number on the edge - that is, we take t steps, add up all the numbers that were on the edges along which we passed, divide by t. Next we take the limit. In this particular game, you can see how profitable it is for players to play and who exactly wins. What happens if Alice goes up? Bob will immediately return the chip back, that is, the total will be 1, Bob is profitable, so Alice has no special meaning to do so. Following the two moves, she returns to the starting position while losing 1. Therefore, let's see what happens with the other version. She went to 0, Bob now has options left and left and down. If he goes left and down, then Alice will have one move, the only one, and she can only go back, and according to the results of these two moves, Bob would lose two. It is unprofitable for him, so you should not do that.
We'll see what happens if it goes strictly to the left. Then Alice had the only move, again they returned to the same point, again Alice acquired 1. Thus, in any case, Alice still wins here. She needs to go here first (2), and then respond with her only moves, and every four moves she will win by 1. This is the best case for Bob, but she will accumulate the win all the same.
Alice wins if the value of the game is positive, and Bob does the opposite. It is known that one of the players always has a winning strategy. And it is also known that there is a positional winning strategy, which is intuitively obvious in general. Positional strategy is when a player's move depends only on where the chip is now. It is pretty obvious that the move should not depend on how they used to go.
So these games are defined. The problem with them is to understand who is winning (or rather, even to understand whether Alice wins, so that the answer is “yes”). This problem is in NP, because if Alice’s winning strategy is given as a certificate, it’s actually easy to check whether this strategy is really a winning one. The same task lies in the coNP, because the certificate that Bob is not losing is his strategy. If you give Bob a strategy, you can check in polynomial time that, no matter how Alice plays, she cannot win.
Now consider a slightly larger problem than the solvability problem. Also look at two more tasks.
- The problem of equivalence of systems. That is, two tropical systems are given, and you need to understand whether they are equivalent.
- The dimension problem. In fact, you need to understand this: the solution of a linear tropical equation is the union of several polyhedra, perhaps infinite. If we take several of them and take a system of them, then there will be an intersection of such polyhedron associations, and this is still the union of several polyhedra. The dimension here can be correctly determined. That is, if we have some kind of tropical polynomial system, then we can look at its solution, find the polyhedron of the maximum difference and call this the dimension of the solution space.
Task: a matrix is given and a number is given, it is necessary to understand whether it is true that the dimension is not less than this number.
All these tasks are considered not only on Z, one can consider them on Z with the addition of infinity. And all of them are polynomially solvable in the classical case.
And in the tropical case, it turns out that no. The table contains all the results. There is a tropical case, there is a min-plus case, three problems are about solvability, equivalence, and dimension. It turns out that the dimension problem in the tropical case is simply NP-complete. There are different links. When there are two references, it means that in the first paper this result is proved over Z, and in the second, over Z∞. There is a significant difference - if there is infinity, then it is less pleasant and much more difficult to prove. Thus, in particular, it turns out that all these problems are equivalent to each other and it does not matter which one of them tries to prove that it lies in P.
How can you look at this picture? There is such an old task - Mean Payoff Games. And it is not yet resolved. We prove that there are quite new tasks that are equivalent to it. Some of them are formulated in certain algebraic terms, in some algebraic structure. Here is the problem of solvability of systems of tropical linear equations. Quite a task like that in a certain algebraic structure, we thus reformulated the task and cyclical games in such new terms. And one can hope that it will be possible to develop the science of tropical polynomials, and when it develops, it will turn out that there we will learn to prove that linear systems can be solved in polynomial time.
What is generally known in the algebraic theory about tropical polynomials? In the linear case, something is known.
There are various analogs of the rank of matrices in tropical algebra. There are actually quite a few of them, they have different meanings, there are different inequalities between them, but nevertheless something is learned there and something is known. There is an analogue of the determinant of the matrix, and it also has good properties there, it is also connected somehow with linear systems.
There is an analogue of the Gaussian triangular matrix.
In the general case, for arbitrary polynomials, much less is known. There is some work on the study of the radical, but especially no progress is visible. The problem of solvability is NP-complete. The system of polynomials is arbitrary, with no restrictions on degrees. In fact, polynomials in degree 2. If we have a system of tropical polynomials in degree 2, then the problem of its solvability is NP-complete.
In the classic case, the problem is already unsolvable.
What is proposed to do? In classical algebra there is a very important result of Hilbert's theorem on zeros.
We will tell about the analogue of this theorem in the tropical case. Here is the weak form of Hilbert's theorem on zeros. This theorem says this: let us have a system of classical polynomials, and we would like to understand that it has no solution. This theorem says that it means constructively that the system of polynomials has no solutions. It turns out that the system of polynomials does not have a general solution if there is their algebraic combination, which is identically 1. That is, simply the polynomial constant 1 is expressed as an algebraic combination of ours. And there is such a result that the system of polynomials does not have a solution if and only if there is such an algebraic combination. In the effective version, it is possible to estimate the degrees of these polynomials g 1 , g k , it can be said that the greatest degree of these products here is no more than 2 dmin (n, k) .
If you try to simply naively formulate an analogue of tropical polynomials, then nothing happens. For the same reason that there is no subtraction. Even if we write just two such polynomials, they have no common roots. No matter how hard we try, whatever algebraic combination we take, zero or one, we will not get it anyway, because this X will not be reduced with anything. Just not provided for such a possibility.
To formulate an analogue of Hilbert's theorem on zeros, we will have to reformulate a little the classical version itself.
To do this, we will have to consider such a Macauley matrix. Let's look at the polynomial system and just such a matrix. N is some parameter number. Its columns are labeled with monomials, the degree is not greater than N, the lines are labeled with polynomials from our system multiplied by monomials. And also degrees are not greater than N. The monomial coefficient in this polynomial is written in the cell of the matrix.
Example: f 1 = 1 + x, f 2 = 2 + y, N = 2.
Such lines are obtained, that is, we can multiply each of these polynomials by some of the variables.
This is actually a generalization of the Sylvester matrix to an arbitrary system of polynomials.
We formulate Hilbert's theorem on zeros in dual form. On the slide - first in the ordinary, and then in the dual. We have a system of polynomials, variables n, degree d. And it turns out that it has a common root if and only if there is a solution to such a linear system.
In principle, it is not difficult to understand. Here it says: we took the polynomials f i , multiply them into different monomials, then put them together. You can look at a polynomial as a vector of its coefficients. When we multiply f i by monomials, we get different lines of the Macauley matrix. And when we fold them, we take a linear combination of the lines of the Macauley matrix. And we want to eventually get a unit. That is, the fact that this system has a solution means that there is no linear combination of rows of the Macauley matrix, which is equal to the vector (1.0, ...). This means that the vector (1,0, ...) does not lie in the linear span of the lines of our matrix. So, we can choose a vector that will be orthogonal to all the lines of our matrix and will not be orthogonal to the vector (1,0, ...).
We define the Macauley matrix in the tropical version. It is defined in the same way: we have a system of polynomials, in the same way the columns are numbered by monomials, in the same way the lines are numbered by polynomials multiplied by monomials, and the same is written in the cells. When there is no monom, the role of zero is played by infinity. We are interested in a tropical linear system with a Macauley matrix. At the same time, we will be interested in such solutions so that 1 does not have 0, that is, not infinity.
We can formulate an analogue of Hilbert's theorem on zeros in dual form for tropical polynomials. Here the wording is exactly the same: the system has a solution if and only if the linear system with the Macauley matrix has a solution. Also, the theorem was proved when the variable is one. The general case is formulated as a hypothesis.
The theorem that this is actually true. Let's consider the system of tropical polynomials, by di we denote their degrees, by - the maximum degree. It turns out that the system has a solution if and only if the Macauley matrix also has a solution. As N you can take this.
In the case when we have no infinity, N is such a thing, it can be estimated as N multiplied by d multiplied by k.
When there is infinity, this is a more complicated thing - it is a polynomial in n, k (see slide). Both of these estimates are to some extent accurate. In fact, this is one of those rare examples when it turns out that it is essentially important whether infinity is there or not.
There is an analogue of this theorem for the min-plus case. The Macauley matrix can be defined in the same way for mine-plus cases, now there will be two of them, and we will already be interested in such a system, a two-sided, mine-plus linear system.
Similarly, we can formulate an analogue of Hilbert's theorem on zeros in the dual form: the min-plus system of polynomials has a solution if and only if such a linear system with Macauley matrices (as n must be taken the same as before).
Initially, this theorem was of dual form - that is, if something does not have a solution, then it has something else. Here this theorem does not have this form. They say that if there is a solution, then there is a solution. If there is no solution, then there is not. This is still not a dual result.
The result of the dual form can also be obtained, and it looks like this. There is a min-plus polynomial system, denoted degrees d. We can say that a system has a solution if and only if it is possible to assemble such a tropical algebraic combination of our polynomials such that for every monomial the coefficient on the left will be greater than the coefficient on the right.
Let there be a system of tropical polynomials. And tropical monomials too. Consider the algebraic combination of g. It is structured as follows: we multiplied the polynomials from f by monomials, and then all this is added. And such an algebraic combination is called nondegenerate if the following occurs:
- for every monomial in g there is such a single g j , there is such a number l (M) that the coefficient of this monomial in this g l (M) is less than all the other terms,
- it is also necessary that these places were different for different monomials.
Example. Consider two such polynomials. And we add them up with such coefficients. These are monomials of zero degree, but they are still monomials. Fold, get this expression. And you can see that the constant monom in the left side has a coefficient of 0, the coefficient in the right side is ½, in the left side it is less, and this is such a place where it is less. In the case of a monomial of degree 1, the coefficient ½ is on the right, the coefficient is on the left. Now it is smaller on the right, and this is the only place where it is smaller. That is, these two monomials are at least in different places. Thus, for these polynomials we can construct a non-degenerate algebraic combination.
It turns out that the existence of such a non-degenerate algebraic combination is the criterion that the system has no solution. In the presence of infinity it is not enough that there is just a nondegenerate algebraic combination, it is also necessary that the constant monomial be finite. Otherwise, there will be a solution in this algebraic combination.
This definition of a non-degenerate algebraic combination, although complicated, is testable.
How are the tropical and min-plus polynomials related? It turns out that in one direction they are connected very simply: if we have a system of tropical polynomials, then it is always possible to construct a system of mines-plus polynomials with the same variables and with the same set of solutions. In the opposite direction there is no such simple information. But it still is: if we have a min-plus system of polynomials, then we can build another tropical polynomial system, which will have twice as many variables, and we can embed the linear space Qn in the linear space Q2n so that all solutions f embeds exactly in all solutions t.
That is, the set of solutions of the system f was a kind of subset in the n-dimensional space, and in t the set of solutions is some kind of subset in the 2n-dimensional space. Nevertheless, one can simply put some solutions biologically into others, they simply correspond to each other.
These two correspondences make it possible to quickly move from the min-plus polynomials to the tropical polynomials. In the results that were listed, as soon as the theorem was proved for one case, it can be immediately translated for the second type of polynomials.
How does the proof of the last series of results work? First there is the tropical theorem on zeros in dual form. It is proved geometrically there. All the main content of the second part actually sits in this theorem. From it it is not very difficult to go to the min-plus case and get just such a theorem.
How is the transition to the theorem out of dual form? In fact, here one can use linear duality for tropical linear systems. It turns out that for them it is also possible to write out linear duality in a simple and understandable form and, having obtained the result, use duality for this linear system (No. 39), interpret the dual system in terms of algebraic combinations, and this will turn out (No. 40). Then from this theorem it is possible, again with the help of the system from the min-plus systems to tropical systems, to obtain (No. 43) the tropical system outside the dual form.
The idea of a geometric proof of the dual form theorem. A system of polynomials on Q has a solution if and only if there is a solution to such a linear tropical system. And in one direction it is simple: if the polynomial system has a solution, then the tropical linear system will also have a solution. It is necessary to remember that the columns Cn of the Macauley matrix correspond to monomials in the variables X. And if there is any solution for the system of polynomials X, we must set i to be equal to this monomial, then in the rows of the Macauley matrix we simply have the coefficients of the polynomial f multiplied by monom. And since X was a solution to the polynomial f, then y will be a solution to the linear equations defined by these lines of the Macauley matrix.
In the other direction is more difficult. It is necessary to do the following: we know that there is some solution to this system, that is, there is some vector Y. We would like to make from it a vector that will have such a form, that is, how it will come from some X.
Firstly, it is useful to fix N = 2, this is the entire substantial case: as soon as it is proved for two, for large n it is generalized instantaneously. We regularly have vectors whose coordinates are numbered by pairs of non-negative integers. For example, these are polynomial coefficients. In fact, they are numbered monomials. The lines of the matrix Macauley and its solution in the same way.
You can look at all these vectors, at all these objects as a set of points in three-dimensional space. The first two coordinates we correspond to the coordinates of the vectors, and the third coordinate corresponds to the values of these coordinates. Then we have polynomials f i from f will correspond to the set of points P fi - this is the set corresponding to their coefficients. . Macauley - . , P fi . Macauley - . .
, Macauley, , , . –. +Y i -Yi. , . P y , Y, , . Y – . ? , Py , . , . , P y , , , . , Y .
, Y , – . , , . - , . , . Y, . .
P fi , , . , .
Y , . : P fi , , – Macauley. Y, , . , , . .
Source: https://habr.com/ru/post/264409/
All Articles