Let $A$ be a set of n relatively prime positive integers. The linear diophantine problem of Frobenius is to find the smallest integer F(A) such that every integer n \geq F(A) can be written as a sum of elements of the set A, with repetitions allowed. For example, if A = {a,b}, then F(A) = (a-1)(b-1). Ramirez Alfonsin proved that this problem is NP-hard by comparison with the integer knapsack problem, and Kannan proved that, for fixed n, the Frobenius problem can be solved in polynomial time by reduction to the covering radius problem in the geometry of numbers. This will be an expository talk on the Ramirez and Alfonsin theorems.