- M. Bellare, O. Goldreich and E. Petrank
- Uniform Generation of NP-Witnesses Using An NP-Oracle
で任意のNP問題の証明を一様ランダムにサンプリングしようという結果です．Jerrum, Valiant, Vazirani の結果でも同様のことができますが，その結果ではNPオラクルだけだと almost uniform だったようです．(完全に一様にするには 
オラクルが必要．)
基本テクニックはハッシュですが，面白いので次回のエントリ辺りから簡単に紹介しようと思います．
