文献

J-GLOBAL ID：201702216480049300   整理番号：17A1774666

短Presburger算術は困難である【Powered by NICT】

Short Presburger Arithmetic Is Hard

著者 (2件)： Nguyen Danny ,  Pak Igor
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： FOCS  ページ： 37-48  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Presburger算術(SHORT PA)中の文の計算量を調べた。短いにより,変数,量化記号,不等式とBoole演算の有界数を持つ文章を意味する入力は線形不等式に関与する整数係数のみから構成されている。m~+2交互量化記号を用いた短PA文の充足可能性であるSigmaP_m完全またはPiP_m完全なことを証明した,最初の量化記号が存在するまたはforall,であった。計数バージョンと制限された系についても解析した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 演算 ,  計算量 ,  *量化記号 ,  不等式 ,  線形性
準シソーラス用語： 有界 ,  *算数 , 【Automatic Indexing@JST】

分類 (2件)： 量子力学一般  (BA06010C) ,  計算理論  (JB02000A)

タイトルに関連する用語 (1件)： 算術