文献

J-GLOBAL ID：201702279674870907   整理番号：17A1357486

分離断片における困難な問題の細粒階層【Powered by NICT】

A fine-grained hierarchy of hard problems in the separated fragment

著者 (1件)： Voigt Marco (Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbruecken, Germany)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： LICS  ページ： 1-12  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 最近,分離されたフラグメント(SF)を導入し,決定可能であることが証明されている。その定義原理は普遍的と実存的定量化変数は原子に発生しないことである。SFの充足可能性問題を決定するのに必要な時間に知られている上限を限量詞交代によって定式化した:ψは量化記号自由SF文∋δ-z→∀x_1∋δ-y→1...∀x_n∋δ-y→_nψが与えられたとき,充足可能性は非決定性n重指数時間で決定できる。本論文では,SF充足可能性の複雑さのよりきめ細かい解析を行った。存在変数の相互作用(短:次数)∂ 文における多くの別々の実存的量化記号ブロック原子における変数の同時発生を介して結合しているかの新しい測度の上限と下限を導出した。我々の主な結果は,次数k以下を持つことを全てのSF文のSF_∂≦kのための充足可能性問題のk NEXPTIME完全である。SF充足可能性は一般に初等的でないことを示し,SFは次数に制約のない定義されるからである。自明な下限を超えて,これまでSF充足可能性の硬さ約知られていない。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】

分類 (3件)： 論理代数  (JB03000H) ,  計算理論  (JB02000A) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (4件)： 断片 ,  問題 ,  細粒 ,  階層