Complexity of the Frobenius problem |
| |
| Authors: | J. L. Ramírez-Alfonsín |
| |
| Affiliation: | (1) Instituto de Matemáticas, Universidad Nacional Autónoma de México, Area de la Investigación Científica Circuito Exterior, Ciudad Universitaria, 04510 México D.F. |
| |
| Abstract: | ![]()
Consider the Frobenius Problem: Given positive integersa1,...,an withai  2 and such that their greatest common divisor is one, find the largest natural number that is not expressible as a non-negative integer combination ofa1,...,an. In this paper we prove that the Frobenius problem is NP-hard, under Turing reductions. |
| |
| Keywords: | 68 Q 15 90 C 10 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
