English Version Русская версия

?????? ??????? ????????
Petrozavodsk State University,Computer Science, dkorzun@cs.karelia.ru

Efficient Algorithms for Solving Linear Diophantine Equations in Nonnegative Integers

A nonnegative linear Diophantine equation (NLDE) is a linear equation with integer coefficients and nonnegative integer solutions. In mathematics and computer science, NLDEs occur in core parts of number theory, discrete mathematics, and algorithm complexity. In applications, NLDEs offer an elegant tool for discrete systems modeling, including logic, optimization, electrical circuits, and data analysis problems. Nevertheless, such models often face the algorithm complexity barrier, since solving NLDEs is a tractable but hard computational problem.

In this paper, we analyze algorithms proposed for solving NLDEs. Different statements of this problem are presented, all are essentially related both to algorithm complexity and to NLDE interpretability in modeling. Solving algorithms are classified depending on what NLDEs they can solve: either the general-form NLDEs (universal algorithms solving any NLDE) or a particular class NLDEs (particular-case algorithms). According to the application needs, we focus our analysis on computational efficiency. Universal algorithms cannot be used for large-dimensional problems because of the complexity barrier. That is why particular-case algorithms merit careful consideration in this study.

A novel approach is introduced for solving NLDE systems. It is based on syntax analysis, since a formal grammar can be assigned to the system. Any solution of the system corresponds to a derivation in the grammar, and thus the solving problem is reduced to parsing. In some cases, it results in very efficient polynomial and pseudo-polynomial algorithms. These particular classes of NLDEs have already found several applications in computer networks modeling.

The state-of-the-art and trends in the area are presented. Focused on the applicability for large-dimension problems, the comparative study shows that the syntactic approach comprises a novel perspective method for theory and practice of computing.