SAT技術の進化と応用 〜パズルからプログラム検証まで〜：3. SATとラムゼー数 〜数学の未解決問題への挑戦〜

• 藤田, 博

• 越村, 三幸

書誌事項

タイトル別名

• SATとラムゼー数 : 数学の未解決問題への挑戦
• SAT ト ラムゼースウ : スウガク ノ ミカイケツ モンダイ エ ノ チョウセン
• SAT Evolution and Applications：3. SAT and Ramsey Numbers

抄録

数学の未解決問題の1つにラムゼー数がある．数学者とコンピュータ科学者の数多の挑戦にもかかわらず，進捗は捗々しくない．ラムゼー数の良い下界を定めるためには，できるだけ大きなラムゼーグラフを1個示せばよい．この目的には，最新のSAT技術の適用が有効である．求めるグラフには何らかの対称性が期待されるが，実際にはその対称性を少し乱したものが正解だったりする．我々はこのことに着目して，探索手法に一工夫凝らしたSATソルバーを開発した．この目論見は当たり，いくつかのラムゼー数の下界について長年停滞していた記録更新に成功した．

収録刊行物

• 情報処理

  情報処理 57 (8), 716-719, 2016-07-15

  東京 : 情報処理学会 ; 1960-

キーワード

• 特集

詳細情報

• CRID: 1050564287860553088
• NII論文ID: 40020914090
• NII書誌ID: AN00116625
• ISSN: 04478053
• NDL書誌ID: 027555333
• Web Site: http://id.nii.ac.jp/1001/00169410/
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I027555333
• 本文言語コード: ja
• 資料種別: departmental bulletin paper
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles