プレスバーガー算術:それは$ EXPSPACE setminus EXP $にあることが知られていますか?

プレスバーガー算術問題の私の理解は、それが二重指数関数的な時間を必要とするが、単指数空間のみを必要とすることであり、これは$
EXPSPACE setminus EXP $にあることを意味する。明らかに、このセットが空でなければ、$ P
subsetneq PSPACE
$は大きな未解決の問題を解決するので、私の理解はおそらく間違っています。私の推理はどこで失敗したのですか?

ベストアンサー

The problem of determining whether a sentence of Presburger
arithmetic is true is in between 2-NEXP and 2-EXPSPACE. When the
number of quantifier alternations is fixed and at least two, the
problem is in between NEXP and EXPSPACE. The existential fragment
is NP-complete. For more details, see e.g. Christoph Haase, Subclasses of Presburger
Arithmetic and the Weak EXP Hierarchy
, CSL/LICS 2014.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です