問題に対するアルゴリズムの計算量を議論する際に「入力」「インスタンス」という言葉が登場する。これらは、アルゴリズムが読み込む文字列という意味では、両者ともに同じ役割を果たすため、特に気にせず同じ意味で用いる人が多いと思う。しかし、実は両者は文脈によっては明確に区別されるべき概念である。
インスタンス（問題例）の概念は計算量理論の言い回しであり、問題に対して具体的な一例を意味する。例えば最短経路問題は問題であるが、具体的なグラフの一つ一つ（を表す文字列）は最短経路問題のインスタンスという。
一方で入力とはアルゴリズムが受け取る文字列である。例えばクラスNPの検証者は、判定問題$L$のインスタンス$x$および、それがYesインスタンスであることを支持する文字列$w$を証拠として受け取る。このとき、$x$と$w$を区切り文字「$,$」を一つ間に入れて連結させて得られる文字列
\[
x , w
\]
を入力と呼ぶ（もしくはチューリング機械において、インスタンスを記述する入力テープと証拠を記述する入力テープを別々に用意しておく設定を考えるならば、組$(x,w)$を入力と定義しても良い）。
また、乱択アルゴリズム（特にモンテカルロ法）の文脈においても同様である。モンテカルロ法とは、計算時間が有限であるものの、出力が誤りうる乱択アルゴリズムである。したがって乱択アルゴリズムを$A(x;r)$のように記述することがある。ここで$x$はインスタンスであり、$r$はランダムシードである。ここでは$;$という記号はインスタンス$x$とランダムシード$r$の役割が根本的に違うため、その区別を明確にするためだけに採用している。このような場合、$x,r$もしくは$(x,r)$がアルゴリズム$A$の入力であり、インスタンス$x$とは異なる文字列になる。
なお、余談であるが「乱択アルゴリズム」の計算モデルには二通りの定義がある。ほとんどの場合はどちらを採用しても構わないので、教科書を執筆するでもない限りは特に気にする必要はないのだが、文脈によって便利な方を採用する。
- 一つ目の定義は二つの遷移関数$\delta_0,\delta_1$を持つチューリング機械であり、便宜上ここでは乱択チューリング機械と呼ぶ。通常のチューリング機械は自身の繊維関数$\delta$を繰り返し適用して計算を進めていくのだが、乱択チューリング機械では各時刻において一様ランダムに$\delta_0,\delta_1$のいずれかを選び、それを適用していく。これは、計算の過程で逐次的にランダムネスを取得する計算モデルなので、オンライン型とも呼ぶ（cf. Goldreich本）。
- 二つ目の定義は、決定的チューリング機械であるが、乱択シード$r$を入力の一部として受け取るモデルである。
