文献

J-GLOBAL ID：201802277222238731   整理番号：18A0344238

強い部分的クローンと時間計算量SAT問題【Powered by NICT】

Strong partial clones and the time complexity of SAT problems

著者 (4件)： Jonsson Peter (Department of Computer and Information Science, Linkopings Universitet, Sweden) ,  Lagerkvist Victor (Institut fuer Algebra, TU Dresden, Dresden, Germany) ,  Nordh Gustav (Kvarnvaegen 6, 53374, Haellekis, Sweden) ,  Zanuttini Bruno (GREYC, Normandie Universite, UNICAEN, CNRS, ENSICAEN, France)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 84  ページ： 52-78  発行年： 2017年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： NP完全問題のための正確な指数時間アルゴリズムの改良拡大している研究分野である。残念なことに,そのような問題の複雑性を比較するための一般的な方法が極めて不足している。本論文では,変数の量を増加させる定数(CV減少)または一定因子(LV減少)による還元によるSAT(S)の複雑さを調べた。クローン理論を用いて,SAT(S)がS≦S′場合SAT(S ′)へのCV還元ような言語に関する≦半順序を得た。この秩序化を用いて,計算的に最も容易なNP完全SAT(S)問題(SAT({ R }))であり,1年に3SATよりも厳密に容易を同定した。SAT({ R })に関連したそれらの複雑さにおける≦と結合した多くの他の言語を決定した。LV減少を用いて,指数時間仮説であるならば,全てのSAT(S)問題である準指数場合にのみ偽ことを証明した。これは次数有界SAT(S)問題をカバーするために拡張した。クローン理論を用いて,CVとLV減少とSAT(S)の複雑性の確実な理解を得た。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *計算量 ,  *クローン ,  半順序 ,  アルゴリズム ,  NP完全問題 ,  言語
準シソーラス用語： 有界 ,  次数 ,  NP完全性 ,  複雑性 ,  *時間計算量 , 【Automatic Indexing@JST】

著者キーワード (5件)： 充足可能性問題 ,  計算の複雑さ ,  クローン理論 ,  普遍的代数 ,  劣指数時間

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

タイトルに関連する用語 (3件)： クローン ,  時間計算量 ,  SAT