文献

J-GLOBAL ID：201902219266358634   整理番号：19A1938927

有限(制約充足)問題を無限にする【JST・京大機械翻訳】

Promises Make Finite (Constraint Satisfaction) Problems Infinitary

著者 (1件)： Barto Libor (Department of Algebra, Faculty of Mathematics and Physics, Charles University Prague, Czechia)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2019  号： LICS  ページ： 1-8  発行年： 2019年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 固定テンプレート投影制約充足問題(PCSP)は,充足可能性とグラフ彩色問題の近似変種を含む固定テンプレートCSPの最近提案された有意な一般化である。有限テンプレート上のすべての現在知られている追跡可能な(すなわち,多項式時間での可解性)PCSPは,ある種の自然な方法で,CSPsを扱うことができる。しかし,そのようなCSPはしばしば無限領域を超えている。無限は,特定の有限領域PCSP,すなわち(1-3-SAT,Not-Alle-Equal-3-SAT)が,P=NPではなければ,自然に扱いやすい有限領域CSPに還元できないことを証明することにより,事実上必要であることを示した。Copyright 2019 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *制約充足問題 ,  近似法
準シソーラス用語： 決定可能性 ,  多項式時間 ,  グラフ彩色 , 【Automatic Indexing@JST】

分類 (2件)： 電力系統一般  (NB02000E) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (1件)： 制約充足