Geodesic
The Frobenius Problem for Classes of Polynomial Solvability
Matematičeskie zametki, Tome 70 (2001) no. 6, pp. 845-853

Voir la notice de l'article provenant de la source Math-Net.Ru

The Frobenius problem is to find a method ($=$ algorithm) for calculating the largest “sum of money” that cannot be given by coins whose values $b_0,b_1,\dots,b_w$ are coprime integers. As admissible solutions (algorithms), it is common practice to study polynomial algorithms, which owe their name to the form of the dependence of time expenditure on the length of the original information. The difficulty of the Frobenius problem is apparent from the fact that already for $w=3$ the existence of a polynomial solution is still an open problem. In the present paper, we distinguish some classes of input data for which the problem can be solved polynomially; nevertheless, argumentation in the spirit of complexity theory of algorithms is kept to a minimum. 
@article{MZM_2001_70_6_a3,
     author = {I. D. Kan},
     title = {The {Frobenius} {Problem} for {Classes} of {Polynomial} {Solvability}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {845--853},
     publisher = {mathdoc},
     volume = {70},
     number = {6},
     year = {2001},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2001_70_6_a3/}
}
TY  - JOUR
AU  - I. D. Kan
TI  - The Frobenius Problem for Classes of Polynomial Solvability
JO  - Matematičeskie zametki
PY  - 2001
SP  - 845
EP  - 853
VL  - 70
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2001_70_6_a3/
LA  - ru
ID  - MZM_2001_70_6_a3
ER  - 
%0 Journal Article
%A I. D. Kan
%T The Frobenius Problem for Classes of Polynomial Solvability
%J Matematičeskie zametki
%D 2001
%P 845-853
%V 70
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2001_70_6_a3/
%G ru
%F MZM_2001_70_6_a3
I. D. Kan. The Frobenius Problem for Classes of Polynomial Solvability. Matematičeskie zametki, Tome 70 (2001) no. 6, pp. 845-853. http://geodesic.mathdoc.fr/item/MZM_2001_70_6_a3/