论文标题
将NEXP完整问题减少到DQBF
Reducing NEXP-complete problems to DQBF
论文作者
论文摘要
我们提供了{\ em依赖性量化布尔公式}（dqbf）满意度的Nexp硬度的替代证明。除了简单之外，我们的证明还为我们提供了一种将NEXP完整问题减少到DQBF的通用方法。 We demonstrate its utility by presenting explicit reductions from a wide variety of NEXP-complete problems to DQBF such as (succinctly represented) 3-colorability, Hamiltonian cycle, set packing and subset-sum as well as NEXP-complete logics such as the Bernays-Schönfinkel-Ramsey class, the two-variable logic and the monadic class.我们的结果表明，DQBF求解器的广泛应用，最近在研究人员中引起了很多关注。
We present an alternative proof of the NEXP-hardness of the satisfiability of {\em Dependency Quantified Boolean Formulas} (DQBF). Besides being simple, our proof also gives us a general method to reduce NEXP-complete problems to DQBF. We demonstrate its utility by presenting explicit reductions from a wide variety of NEXP-complete problems to DQBF such as (succinctly represented) 3-colorability, Hamiltonian cycle, set packing and subset-sum as well as NEXP-complete logics such as the Bernays-Schönfinkel-Ramsey class, the two-variable logic and the monadic class. Our results show the vast applications of DQBF solvers which recently have gathered a lot of attention among researchers.
