共同研究・競争的資金等の研究課題

2011年 - 2013年

サンプリングアルゴリズムの新提案

文部科学省  科学研究費補助金(若手研究(B))
  • 山本 真基

課題番号
23700025
担当区分
研究代表者
配分額
(総額)
2,080,000円
(直接経費)
1,600,000円
(間接経費)
480,000円
資金種別
競争的資金

本研究で行えたことは主に次の二つである.1: グラフのパスおよびサイクルの数え上げが#P完全(計算困難な問題)である.2: グラフのパスおよびサイクルの数え上げが(RP≠NPのもと)近似不可能(近似計算困難な問題)である.パスやサイクルはグラフ構造として木に近い性質を持っており,それゆえ,この結果はTutte多項式の近似計算可能性・不可能性において,未解決となっている領域である木の数え上げの近似可能性・不可能性に向けて何かしらの知見を与えていると期待できる.

リンク情報
URL
https://kaken.nii.ac.jp/d/p/23700025.ja.html