权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

计算问题的并行性和非并行性

基本信息

批准号：
05780239
负责人：
陳致中
金额：
$ 0.26万
依托单位：
Mie University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至无数据
项目状态：
已结题

项目摘要

本研究では極大化問題(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-完全(多項式時間完全)な極大化問題が存在する。ゆえに、連続性を持つ極大化問題は一般的に並列化不能である。

This study focuses on the possibility of parallelization of the maximization problem (maximality problem). The maximization problem and the optimization problem (optimization problem) are similar to those in nature. In order to study the main point of view of the main point of view, the rate of each problem is different, and the possibility of parallelization is included in the general discussion and listing of the general discussion of the possibility of parallelization. in this paper, we discuss the general discussion of the possibility of parallelization, and list the general discussion of the possibility of parallelization. In this study, we will discuss the general group proposal for instance problems (instance) collection examples-solving problems (instance-solution relation). The basic data and the possibility of parallelization are all defined by the basic data, the possibility of parallelization, the size of the problem, the hereditariness property, the definition of the definition, the definition, the definition. The definition of connectivity (continuity) is defined as follows: major problems Q connectivity support, Q any connection, any two-way solution to slots, real information, etc. S