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

2001年 - 2003年

命題論理の証明の複雑さに関する研究

日本学術振興会  科学研究費助成事業  基盤研究(C)

課題番号
13680422
体系的課題番号
JP13680422
配分額
(総額)
3,000,000円
(直接経費)
3,000,000円

コンピュータサイエンスにおいて、最も中心的な問いのひとつが、与えられた関数(グラフ)を計算するための最も効率のよいアルゴリズムは何か?と言う問題である。これは、ひとつには「P=?NP」問題に集約される。この課題に対して、ロジックからのアプローチとしては、次の2つが考えられる
1.与えられた命題論理の体系に対し、その体系では多項式サイズの証明が存在しないような定理群を発見する
2.与えられた2つの命題論理の体系が相対的にどちらの方が証明効率がよいか
本研究においては、タブロー法とレゾリューション法の証明の複雑さに関して研究を進めた。この2つの体系は、多くの自動証明機のエンジンとして採用されていることを追記しておく。その結果、1970年代から未解決であった、さまざまなタブロー法のバリエーション間の相対的証明効率の問題を完全解決した。まず、自動証明機のエンジンとして最も採用されているclausal tableauというタブローは一般的なタブローに比べて、superpolynomial-timeな遅延があることを発見した。また、resolution法はタブロー法に比べてexponentialのスピードアップがあると信じられてきたが、それは誤りであり、resolution法はタブロー法に比べて、擬似多項式時間分しかスピードアップしないことを論理的に証明した。
一方、本研究においては、clausal tableau法にシンメトリーという推論を付け加えることによって、新しい体系SCRを構築し、その証明力についてさまざまに考察した。結果、resolutionでは短く証明できない多くの組み合わせ論的な問題がSCRでは多項式サイズの証明があることがわかった。SCRはタブロー法をベースとしているため、自動証明に応用することができ、これをGodzillaという自動証明機として実現した。

リンク情報
KAKEN
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680422
ID情報
  • 課題番号 : 13680422
  • 体系的課題番号 : JP13680422

この研究課題の成果一覧

論文

  2