他の側から見た一般値CSPの複雑性【JST・京大機械翻訳】

Carbonnel Clement; Romero Miguel; Zivny Stanislav

プレプリント

J-GLOBAL ID：202202219671802540 整理番号：21P0005225

他の側から見た一般値CSPの複雑性【JST・京大機械翻訳】

The complexity of general-valued CSPs seen from the other side

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2017年10月09日プレプリントサーバーでの情報更新日： 2021年10月03日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

制約充足問題(CSP)は,2つの構造の間の同形写像に関係する。制限された左手側構造のCSPsに対して,ダルマウ,コラ炎,およびVardi[CP’02],Grohe[FOCS’03/JACM’07,およびAtserias,Bulatov,およびDalmau[ICALP’07の結果により,多項式時間可解性(複雑性理論的仮定に対する被験者)の正確な境界と,有界ツリー幅モジュロホモモルフィック等価性としての有界一致アルゴリズム(非条件的)による可解性を確立した。一般値制約充足問題(VCSP)は,2つの価値構造間の同形写像に関係するCSPの一般化である。制限された左手側値構造を有するVCSPsに対して,多項式時間可解性(複雑性理論的仮定に対する主題)の正確な境界とSherali-Adams LP階層のk-thレベルによる可解性(無条件)を確立した。また,解の発見と扱いやすいケースの認識に関する関連問題に関する結果も得た。後者はデータベース理論に応用されている。【JST・京大機械翻訳】

, , , , , ,
, , , , 【Automatic Indexing@JST】

計算理論 , 人工知能

前のページに戻る