フロベニウスの硬貨交換問題

フロベニウスの硬貨交換問題（フロベニウスのこうかこうかんもんだい）とは、指定された硬貨だけではぴったり払えない最大の金額を求める数学の問題である。フロベニウスの問題、シルベスターの切手問題とも呼ばれる。数学者フェルディナント・ゲオルク・フロベニウスにちなんで名付けられた。例えば、3円と5円のコインだけでは作れない最大の金額は7円である。コインの種類の特定の組み合わせに対するこの問題の解は、その組み合わせに対するフロベニウス数と呼ばれる。フロベニウス数は、硬貨の額面が互いに素である限り存在する。 x円とy円の2種類の硬貨しかない場合は、フロベニウス数の公式が存在し、xy − x − y である。硬貨が3種類以上の場合の公式は未解決問題である。しかし、任意の種類の硬貨に対して、（硬貨の種類の数の「対数」に対して）多項式時間でフロベニウス数を計算するアルゴリズムが存在する。硬貨の種類に対して多項式時間で解けるアルゴリズムは見つかっておらず、硬貨の種類に制限を設けない一般的な問題はNP困難である。