2008-10-11から1日間の記事一覧
M. Bellare, O. Goldreich and E. Petrank Uniform Generation of NP-Witnesses Using An NP-Oracle で任意のNP問題の証明を一様ランダムにサンプリングしようという結果です.Jerrum, Valiant, Vazirani の結果でも同様のことができますが,その結果ではNP…
M. Bellare, O. Goldreich and E. Petrank Uniform Generation of NP-Witnesses Using An NP-Oracle で任意のNP問題の証明を一様ランダムにサンプリングしようという結果です.Jerrum, Valiant, Vazirani の結果でも同様のことができますが,その結果ではNP…