文献

J-GLOBAL ID：202202254849246099   整理番号：22A0321618

(m)CPネット上の選好集約のための複雑性結果:最大およびランク投票【JST・京大機械翻訳】

Complexity results for preference aggregation over (m)CP-nets: Max and rank voting

著者 (2件)： Lukasiewicz Thomas (Department of Computer Science, University of Oxford, United Kingdom) ,  Malizia Enrico (DISI, University of Bologna, Italy)
資料名： Artificial Intelligence  (Artificial Intelligence)
巻： 303  ページ： Null  発行年： 2022年 
JST資料番号： E0180C  ISSN： 0004-3702  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： コンビナトリアルドメイン上の凝集選好は,AIにおいて多くの応用を持つ。コンビナトリアル選好の指数関数的性質のため,コンパクトな表現が必要であり,条件付きceteris paribus選好ネットワーク(CPネット)は,最も研究されたコンパクトな表現形式である。文献において広範な複雑性解析を受けた個々のCPネット上の結果優位性の問題と異なり,mCPネット(CPネット上のグローバル投票/参照集約)は,公開問題として文献において複数回報告されているにもかかわらず,そのような完全な複雑性特性化を欠いている。mCPネットに対する初期複雑性解析を,最近のみ行い,そこでは,パレートと多数支配意味論を研究した。本論文では,mCPネットの複雑性をさらに探索し,最大およびランク投票方式を考慮した場合,mCPネットにおける優越意味論の正確な複雑性解析を与えた。特に,最大投票の下での支配決定はΘ2P完全であり,一方,最適結果を決定し,最大投票下のそれらの存在は,それぞれΠ2PおよびΣ3Pに対して完全であった。また,最大投票の下で,最適結果を決定することは,Π2P完全であり,それらの存在を決定することは,Π2P-ハードおよびΣ3Pであった。ランク投票に関しては,mCPネットがランク最適結果を持つかどうか決定することとは別に,すべてのmCPネットがランク最適結果を持つので,考慮したすべての他のランク投票タスクは扱いやすく,P.面白いことに,これらの問題はPだけでなく,P-ハード(従ってP-完全)にもなることを示した。さらに,mCPネットがPareto最適結果を持つかどうか決定することは,多項式時間で実現可能であることが知られており,CPネットに対する様々なタスクがP完全であるだけでなく,実際にP完全であることを証明した。これらの結果は,P完全問題が(現在は)本質的に逐次的であると思われ,従って,それらは高度に並列な計算から利益を得ることができないので,興味深い洞察を提供する。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 凝集 ,  多項式 ,  意味論 ,  ネットワーク ,  指数関数 ,  表現型 ,  計算量 ,  好み ,  *投票 ,  性質 ,  キャラクタリゼーション
準シソーラス用語： Pareto最適 ,  複雑性 ,  多項式時間 , 【Automatic Indexing@JST】

著者キーワード (11件)： 選好 ,  組合せ選好 ,  選好集約 ,  CPネット ,  mCPネット ,  投票 ,  最大投票 ,  ランク投票 ,  計算の複雑さ ,  多項式階層 ,  P硬度

分類 (2件)： 人工知能  (JE08000Z) ,  計算理論  (JB02000A)

タイトルに関連する用語 (6件)： CP ,  ネット ,  選好 ,  集約 ,  複雑性 ,  投票