抄録

◎河瀬康志（東工大）・牧野和久（京大）・勢見賢人（トーア再保険）

本研究では、最適合成順問題を導入し、その計算複雑性を議論する．入力としてn個の実関数f₁,...,f_nと実数cが与えられる．このとき，最大k合成順問題は，与えられたkについて，f_σ(k) ◦ … ◦f_σ(1)(c)を最大化するn次の置換σを求める問題である．特に，k=nの場合を最大全合成順問題と呼び，kも自由に選べる中で最大化する問題を最大部分合成順問題と呼ぶ．
本研究では，単調非減少な1次関数に対する最大全合成順問題，最大部分合成順問題に対しO(n log n)時間アルゴリズムを与え，最大k部分合成順問題に対しO(kn²)時間アルゴリズムを与える． また，与えられる関数を高々2区分からなる区分線形単調関数に限っても，これらの問題はNP困難となることを示す．