一様コスト RAM モデル

計算機は、番地 $0, 1, 2, \ldots$ で添字づけられた記憶セルの列と、有限個のレジスタを持つとする。次の各操作を基本演算と呼び、いずれも 1 単位時間で実行されるものとする。

1. 定数、レジスタ、および番地を指定した記憶セルからの読み出しと書き込み
2. 整数・実数の加減乗除と比較
3. 条件分岐と無条件分岐

さらに、1 個の記憶セルには $O(\log n)$ ビットの語（$n$ は入力サイズ）が格納できるものとする。