Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz (Q650840): Difference between revisions

Systems of polynomial equations over a field can yield compact models of difficult combinatorial problems and they can be used to prove combinatorial results. In particular, existence of the solutions of the systems means that the combinatorial objects have the properties captured by the systems. This is called the combinatorial feasibility problem. However, because of the efficiency reason, the systems of polynomial equations have not been widely used for computation. The paper under review proposes a method for practical computations. The key idea is to use the Nullstellensatz to generate a finite sequence of linear-algebra systems, which will eventually become feasible if and only if the combinatorial problem is infeasible. Namely, let \(f_1,\dots, f_s \in {\mathbb K}[x_1,\dots, x_n]\), where \({\mathbb K}\) is a field, be a set of polynomials encoding a combinatorial problem. Then the system of equations \(f_1 = \cdots =f_s=0\) has no solution in \(\overline{{\mathbb K}}^n\), where \(\overline{{\mathbb K}}\) is the algebraic closure, if and only if the ideal \((f_1,\dots, f_s) = {\mathbb K}[x_1,\dots, x_n]\), in other words, we have an equation \(1 = \sum_{i=1}^s \beta_i f_i\) for some \(\beta_i\in {\mathbb K}[x_1,\dots, x_n]\). This equation is called a Nullstellensatz certificate. Then the main part of the computation for combinatoriay feasibility is to find the polynomials \(\beta_i\). This is carried out by a sort of try-and-error method. We first take \(\beta_i\) of some degree with general coefficients, which yields a linear-algebra system of the general coefficients and we try to solve this system with a suitable algorithm for linear algebra. If we find that the linear-algebra system has no solution, then we replace \(\beta_i\) by polynomials of higher degrees. The crucial part of the algorithm is the upper bound of the degrees of the polynomials \(\beta_i\). Theoretically the bound exists, which ensure termination of the algorithm, but for the efficiency we need much smaller bound. The authors adopt the bound given by \textit{D.\ Lazard} [Algèbre linéaire sur \(K[X_1,\dots,X_n]\) et élimination'', Bull. Soc. Math. Fr. 105, 165--190 (1977; Zbl 0447.13008)], which shows high computational efficiency for combinatorial problems on graphs. The author also discuss other optimization methods such as using finite fields, appending certain valid bu redundant polynomicals, branching, alternative Nullstellensatz and deleting suitable equation for reducing the bound of \(\beta_i\)s and use of symmetries of the equation for efficient computation of liear-algebra systems. Finally experimental results with comparison of other systems are presented.