マルコフ連鎖 とは， 状態遷移が現在の状態のみに依存する 確率過程 である． （以降では，状態の個数が有限のマルコフ連鎖を扱う．） マルコフ連鎖は， 次のように有向グラフで表現される： 各頂点は一つの状態を，各辺は一つの遷移を， 更に，辺の重みはその辺に対応する状態遷移の確率を表す． 一方， モンテカルロ法 とは， サンプリング（やシミュレーション）を用いて 所望の値を求める計算手法のことである． 確率空間 (Ω,P) のサンプリングとは， 標本空間 Ω からある標本点を確率 P に従って抽出することである． サンプリングにマルコフ連鎖を用いた場合， そのモンテカルロ法は，特に， マルコフ連鎖モンテカルロ法 （Markov chain Monte Carlo methods，以降，MCMC 法と略す）と呼ばれる． 確率空間 (Ω,P) のサンプリングにマルコフ連鎖を用いるとは， 大まかには， 以下のようなアルゴリズムでサンプリングすることである：
MCMC 法は， 理論計算機科学（Theoretical Computer Science） において強力かつ重要な道具であり， 多くの研究者が注目を寄せている研究分野である． （一般的な MCMC 法は [1] を， 理論計算機科学における MCMC 法 は [2], [3], [4] を参照．）
１９７９年，Leslie Valiant が ＃Ｐ と いう計算量クラスを定義した． これは， 制約を満たす解の個数を求める関数問題のクラスである． （ＰやＮＰなどは YES/NO 判定をする決定問題である．） 更に， ＃Ｐの中で「最も難しい」問題を＃Ｐ完全と定義した． （詳しくは ここ を参照．） ＃Ｐの定義より， 充足可能性問題（ＳＡＴ）の数え上げ （与えられる CNF 論理式の充足解の個数を求める問題） が＃Ｐ完全であることは容易に確認できる． この他にも， 頂点彩色問題，独立頂点集合問題，ハミルトン閉路問題など， 多くのＮＰ完全問題の数え上げが＃Ｐ完全である． （ただし， すべてのＮＰ完全問題の数え上げが＃Ｐ完全となるかはまだ分かっていない．） 一方，これらとは異なり， 多項式時間計算可能な問題の数え上げが＃Ｐ完全となることもある． 2-SAT 問題の数え上げ， 完全マッチング問題の数え上げがその代表である． 更に，例えば， 頂点彩色問題の数え上げにおいて， 頂点次数の最大が Δ であるようなグラフ の 2Δ-彩色の個数を求める問題も＃Ｐ完全である． （この数え上げに対する決定問題， つまり， 頂点次数の最大が Δ であるようなグラフ に 2Δ-彩色が存在するか， という問題は多項式時間計算可能な問題である． なぜなら，そのようなグラフは (Δ+1)-彩色可能であるので．）
ここで，以下の基本的な事実を確認しておく：
＃Ｐ完全問題が多項式時間で解けるなら， ＮＰ完全問題も多項式時間で解ける．このことは， P≠NP ならば＃Ｐ完全問題は多項式時間で解けないことを意味する．
MCMC 法は， このような＃Ｐ完全問題を近似して（多項式時間で）解くことに用いられる． 例えば，次のような，基本的で重要なグラフの問題の数え上げを近似して 解くことに用いられる：
このように，MCMC 法は， （多項式時間で正確に解くのが難しいと思われる）問題を 近似して解くことに用いられる． 一方で， 多くの＃Ｐ完全問題が近似困難であることも示されている [5]． （ただし，この近似困難性は， ＮＰが計算量クラス ＲＰ に包含されないことを仮定している．） 例えば， 頂点彩色問題の数え上げは， 与えられるグラフが任意であれば近似困難となる． （MCMC 法で頂点彩色問題の数え上げが近似して解けると示されたのは， 与えられるグラフの次数に制限がある場合である． 例えば， k-彩色の数え上げであれば， 与えられるグラフの頂点次数の最大が k/2 以下である場合である．） この他に， 独立頂点集合問題，ハミルトン問題，頂点被覆問題の数え上げは （一般には）近似困難である． もっと一般的に次の定理が成り立つ：
定理（Dyer, Goldberg, Greenhill, and Jerrum, [5]） 任意のＮＰ完全問題 A の数え上げ #A は近似困難である．この定理からは導かれない近似困難な問題も存在する． #2-SAT 問題がその代表である． （パスの数え上げや閉路の数え上げなども近似困難である．） このように多くの＃Ｐ完全問題が近似困難である． これに比べれば， MCMC 法により近似可能であると示された＃Ｐ完全問題は （残念ながら）少数である． （もっとも， MCMC 法は 少なくとも一つの解を多項式時間で見つけられることを前提としているので， 対応する決定問題がＮＰ完全であれば， その数え上げに MCMC 法を適用するのはかなり難しい．）
一方で， 近似可能か近似困難かが分かっていない問題が数多くある． 代表的な問題を以下にあげておく：