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