離散的問題に対する計算量の解析

P=NP問題などいくつかの重要な未解決問題の解決には計算量の下界を求める強力な手法の開発が不可決である。ナップザック問題、クリーク問題などNP完全な離散的問題を対象として、計算量の下界を求める研究を従来から行ってきたが、今年度もこれらについてさらに考察を深めた。とくに、これらの問題に対応するブール関数列の素子計算量を調べるため、n変数ブール関数に関する演算をn次元超立方体上の集合演算に置きかえて、計算量を超立方体の部分集合で特徴づける試みについて基礎的な研究を行った。これらの成果についてはまだ雑誌等に発表する段階に至ってはないが、いくつかの新しい知見が得られており、今後さらに研究を続ける予定である。ブール関数の拡張である多値論理関数についても、とくにクローン (clone)の分類について研究を行い、いくつかの成果をおさめた。クローンの分類にとって重要な役割を果たすと思われる「本質的極小クローン」という概念を数年前に町田が導入したが、この本質的極小クローンについて今年度2つの論文を発表した。1つは、無限集合上の本質的極小クローンの中に2変数関数をすでに無限個含むものが存在すること、すなわち、本質的極小クローンの中には大きなクローンが存在することを示したものである。もう1つの論文では、有限集合上の本質的極小クローンで2変数関数によって生成されるものを研究対象とし、これらをすべて決定することを試みた。この決定にはいくつかの場合分けが必要になり、そのうちの極めて難しい1,2の場合についてはまだ分類が完成していない。今後、残された場合の分類の完成に努めるとともに、3変数以上の関数で生成される本質的極小クローンについても分類の研究を試みる予定である。

P=NP問題などいくつかの重要な未解決問題の解決には計算量の下界を求める強力な手法の開発が不可決である。ナップザック問題、クリーク問題などNP完全な離散的問題を対象として、計算量の下界を求める研究を従来から行ってきたが、今年度もこれらについてさらに考察を深めた。とくに、これらの問題に対応するブール関数列の素子計算量を調べるため、n変数ブール関数に関する演算をn次元超立方体上の集合演算に置きかえて、計算量を超立方体の部分集合で特徴づける試みについて基礎的な研究を行った。これらの成果についてはまだ雑誌等に発表する段階に至ってはないが、いくつかの新しい知見が得られており、今後さらに研究を続ける予定である。ブール関数の拡張である多値論理関数についても、とくにクローン (clone)の分類について研究を行い、いくつかの成果をおさめた。クローンの分類にとって重要な役割を果たすと思われる「本質的極小クローン」という概念を数年前に町田が導入したが、この本質的極小クローンについて今年度2つの論文を発表した。1つは、無限集合上の本質的極小クローンの中に2変数関数をすでに無限個含むものが存在すること、すなわち、本質的極小クローンの中には大きなクローンが存在することを示したものである。もう1つの論文では、有限集合上の本質的極小クローンで2変数関数によって生成されるものを研究対象とし、これらをすべて決定することを試みた。この決定にはいくつかの場合分けが必要になり、そのうちの極めて難しい1,2の場合についてはまだ分類が完成していない。今後、残された場合の分類の完成に努めるとともに、3変数以上の関数で生成される本質的極小クローンについても分類の研究を試みる予定である。