文献

J-GLOBAL ID：201802234162708071   整理番号：18A0344254

裏口不均一クラスSATとCSPの【Powered by NICT】

Backdoors into heterogeneous classes of SAT and CSP

著者 (5件)： Gaspers Serge (UNSW and NICTA, Sydney, Australia) ,  Misra Neeldhara (Indian Institute of Science, Bangalore, India) ,  Ordyniak Sebastian (Algorithms and Complexity group, TU Wien, Vienna, Austria) ,  Szeider Stefan (Algorithms and Complexity group, TU Wien, Vienna, Austria) ,  Zivny Stanislav (University of Oxford, Oxford, UK)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 85  ページ： 38-56  発行年： 2017年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,バックドア変数の異なるインスタンス化について種々の基本的なクラスに属することを例をもたらすことを可能にすることにより,SATとCSPのための強および弱裏口集合の古典的概念を拡張しベースクラスの癒合が不均一塩基クラスを形成する。裏口集合不均一塩基クラスにはバックドア集合均一のものよりはるかに小さくなる可能性があるので,それらがより望ましいが見出しに硬かった。SATとCSPのための不均一系塩基クラスに強いと弱い裏口集合を検出する問題の詳細な複雑性景観を描いた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *不均一系
準シソーラス用語： 複雑性 , 【Automatic Indexing@JST】

著者キーワード (4件)： 制約充足 ,  充足可能性 ,  バックドア集合 ,  パラメータ化された複雑性

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 不均一 ,  クラス ,  SAT ,  CSP