Given natural numbers with greatest common divisor , find the largest natural number that is not expressible as a linear non-negative integer combination of the .
For the answer is given by . The general problem is -hard.
For a fixed there is a polynomial-time algorithm to solve the Frobenius problem, [a1].
|[a1]||R. Kannan, "Lattice translates of a polytope and the Frobenius problem" Combinatorica , 12 (1992) pp. 161–172|
|[a2]||L. Lovász, "Geometry of numbers and integer programming" M. Iri (ed.) K. Tanabe (ed.) , Mathematical Programming , Kluwer Acad. Publ. (1989) pp. 177–202|
Frobenius problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Frobenius_problem&oldid=16167