確率的アルゴリズムと近似アルゴリズム

多項式時間(Polynomial)アルゴリズムが知られていない問題を解くときに用いる。用いると言っても、『答えとして受け入れられる答え』が出ることが知られている必要がある。
『答えとして受け入れられる答え』の担保が示されていることが条件で、かつ、計算量が確かに『節約』され、『実行してもよい計算量』であることが示されている必要がある