Transdichotomous model とは

計算複雑性理論、より具体的には整数データを用いたアルゴリズムの解析では、変換器モデルは機械語サイズが問題サイズに一致すると仮定されたランダムアクセス機械の変形である。このモデルはMichael FredmanとDan Willardによって提案されました。その名前は "機械モデルと問題サイズの間の二分法が合理的な方法で交差されているためです"。
ソートされる整数がn個存在する整数ソートのような問題では、変換モデルは、各整数が1ワードのコンピュータメモリに格納され、1ワードの演算がオペレーションごとに一定の時間をとり、 1ワードに格納できるビット数は少なくともlog2nです。このモデルの複雑さ分析の目標は、入力値または機械語の実際のサイズではなく、nにのみ依存する時間境界を見つけることです。整数計算のモデリングでは、機械語のサイズが制限されていると想定する必要があります。これは、無制限の精度を持つモデルが不合理に強力なためです(多項式時間でPSPACE完全問題を解くことができる)。変換モデルは、このタイプの最小限の仮定をしています。いくつかの制限があり、入力データへのランダムアクセス索引付けを可能にするのに十分な大きさです。
整数ソートへの応用と同様に、経時的なモデルは、優先度キューの設計や計算ジオメトリやグラフアルゴリズムの問​​題にも適用されています。