計算問題の並列化可能性と並列化不能性

点击翻译按钮获取中文摘要

本研究では極大化問題(maximality problem)の並列化可能性と並列化不能性に焦点を当てた。極大化問題は、最適化問題(optimization problem)の自然な近似となるので、盛んに研究されてきた。しかし、極大化問題に関する従来の研究の主眼点は各問題に個別的で効率のよい並列アルゴリズムを見出すことであり、並列化可能性についての一般的な議論や並列化不能性についての研究がほとんど行なわれてこなかった。そこで、本研究ではまず、極大化問題を扱うための一般的な枠組を次のように提案した:極大化問題は実例(instance)の集合と実例-解関係(instance-solution relation)との対である。この枠組に基づいて、並列化可能性が知られている極大化問題のほとんど全部持っている性質、遺伝性(hereditariness property)を次のように定義した:極大化問題Qが遺伝性を持つとは、Qの任意の実例xとxの任意の解sに対し、sのどの部分集合もxの解であるときをいう。また、遺伝性の拡張として連続性(continuity)を次のように定義した:極大化問題Qが連続性を持つとは、Qの任意の実例xとxの任意の二つの解sとs′に対して、sがs′を真に含む(s′⊂s)ならば、sがxの解であることを保ちながらsの一部の要素をある順序で一つずつ削っていくとs′に到達できるときをいう。連続性は遺伝性をできるだけ小さく拡張したものである。並列化可能で遺伝性を持つ極大化問題が多く知られているのに対し、並列化可能で連続性を持つ極大化問題はあまり知られていない(いくつか知られているが、その並列可能性の証明が非常に複雑である)。本研究では、このような現象の理論的根拠として、次の結果を証明した:連続性を持ち、かつ、P-完全(多項式時間完全)な極大化問題が存在する。ゆえに、連続性を持つ極大化問題は一般的に並列化不能である。