トポロジーは関連(無限領域制約充足問題に対する二分予想において)【JST・京大機械翻訳】

Bodirsky Manuel; Mottet Antoine; Olsak Miroslav; Oprsal Jakub; Pinsker Michael; Willard Ross

プレプリント

J-GLOBAL ID：202202218377342992 整理番号：22P0054356

トポロジーは関連(無限領域制約充足問題に対する二分予想において)【JST・京大機械翻訳】

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)

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

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

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

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

(無限)有限有界均一構造状態のリダクトの制約充足問題(CSPs)に対する代数的二分推定は,テンプレートのモデル完全コアが擬Sトリガーs多型を持ち,NP完全がそうでなければ,このようなCSPsは多項式時間扱いやすい。この予想に関連する重要な疑問の一つは,有限構造の場合と同様に,擬似Sトリガーs多型を持つ条件が,高さ1の一定集合,すなわち,機能的記号の営巣を含まない同一性の固定集合を満たす多型を持つ条件によって置換できるかどうかである。著者らは,その多型がこれらの同一性を満たさないが,そのCSPが扱いやすい構造である,高さ1アイデンティティの各々の非自明な集合を構築することにより,この疑問に負の答えを提供する。二分切開の等価定式化は,構造の多型による非自明な高さ1同一性の局所満足を介してCSPの扱いやすさを特徴付ける。著者らは,非自明な高さ1同一性の局所的満足とグローバル満足が,二重指数軌道成長より少ないω-カテゴリー構造のために異なり,それによって,そのような構造の代数理論における主な開放問題の1つを解決することを示した。【JST・京大機械翻訳】

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

計算理論 , システム・制御理論一般

, , ,

前のページに戻る