結び目の非自明性判定問題に対する対話型証明系について
スポンサーリンク
概要
- 論文の詳細を見る
Hass-Lagarias-Pippengerは結び目理論,絡み目理論における様々な決定問題の計算量を解析した.その中で3次元球面内の結び目の自明性判定問題が,NPに含まれることを証明し,この問題がNP∩co-NPに含まれるだろうと予想している. HassはAlgo,Thurstonと共同で結び目の自明性判定問題を含む一般の3次元多様体における種類判定問題がNP-完全であることを証明した.我々は自明性判定問題の補問題である非自明性判定問題を解く対話型証明系を構成し,この問題がIP(2)に含まれること,つまり,自明性判定問題がAM∩co-AMに含まれることを示した.このことから,自明性判定問題がNP-完全ならば？^P_2=Π^P_2であることになり,自明性判定問題はNP-完全ではないと予想される.
- 社団法人電子情報通信学会の論文
- 2003-01-17
著者
-
谷 聖一
日本大学文理学部
-
原 正雄
東海大学理学部情報数理学科
-
山本 慎
中央大学理工学部数学科
-
山本 慎
Department Of Mathematics Chuo University
-
原 正雄
Department Of Mathematical Sciences Tokai University
関連論文
- 2橋絡み目のHOMFLY多項式を計算する高速なアルゴリズム (コンピュテーション)
- 国際情報オリンピックエジプト大会参加報告
- Google Maps APIを利用した時空間分析ツールの試作 : 喜多村緑郎日記を対象として
- 喜多村緑郎文庫のデジタルアーカイブ化--多面的利用の可能性 (学術フロンティア推進事業 平成19年度(18年度後期分を含む)の研究報告)
- 2橋絡み目のHOMFLY多項式を計算する高速なアルゴリズム
- 甲状腺腫瘍のシンチグラム所見--甲状腺癌鑑別の可能性について
- A FAST ALGORITHM FOR COMPUTING JONES POLYNOMIALS OF MONTESINOS LINKS
- Fast Algorithms for Computing Jones Polynomials of Certain Links (Evolutionary Advancement in Fundamental Theories of Computer Science)
- ブレイド群における共役問題の計算量について
- 結び目の非自明性判定問題の計算量について (計算機科学基礎理論の新展開)
- 表編集のアルゴリズム (計算機科学基礎理論の新展開)
- 結び目の非自明性判定問題に対する対話型証明系について
- A-23 band generatorを用いたブレイドの標準型を構成するアルゴリズム(離散アルゴリズム(2),A.アルゴリズム・基礎)
- A-2 クリーク発見問題に対する量子アルゴリズム(計算量・量子計算,A.アルゴリズム・基礎)
- LA-8 Arborescent絡み目に対するジョーンズ多項式計算アルゴリズム(A. アルゴリズム・基礎)
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- ブレイド群における共役問題の計算量について
- グラフ同型写像の数え上げ問題に対するアルゴリズムについて
- Arborescent リンクダイアグラムのKauffmanブラケット多項式を決定する多項式時間アルゴリズム
- 西野,哲朗著 : 中国人郵便配達問題=コンピュータサイエンス最大の難関, 講談社選書メチエ148(1999).
- 絡み目のJones多項式の最高次数の計算について
- 絡み目のJones多項式の計算 (計算モデルとアルゴリズム)
- グラフ同型写像の数え上げ問題に対するアルゴリズム
- A Fast Algorithm for Computing Jones Polynomials of Montesinos Links(Theory of Computer Science and Its Applications)
- 2-bridge diagramのHOMFLY-PT多項式の計算について
- シンチカメラと小型電算機システムによる肝シンチグラムの欠損像検出能力の検討
- 絵葉書に描写された都市景観の持つ感性情報の分析とその応用 : ハルビンの歴史的絵葉書資料を事例として(コミュニケーション支援及びヒューマンコミュニケーション一般)
- 絵葉書に描写された都市景観の持つ感性情報の分析とその応用 : ハルビンの歴史的絵葉書資料を事例として(コミュニケーション支援及びヒューマンコミュニケーション一般)
- N-004 デジタルアーカイブ化されたハルビン絵葉書の印象調査(人文科学とコンピュータ,N分野:教育・人文科学)
- 絵葉書に描写された都市景観の持つ感性情報の分析とその応用 : ハルビンの歴史的絵葉書資料を事例として
- 絵葉書に描写された都市景観の持つ感性情報の分析とその応用 : ハルビンの歴史的絵葉書資料を事例として