Reducing NEXP-complete problems to DQBF
Journal
Proceedings of the 22nd Conference on Formal Methods in Computer-Aided Design, FMCAD 2022
ISBN
9783854480532
Date Issued
2022-01-01
Author(s)
Chen, Fa Hsun
Huang, Shen Chang
Lu, Yu Cheng
TONY TAN
Abstract
We present an alternative proof of the NEXP-hardness of the satisfiability of 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önflnkel-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.
Subjects
Dependency quantified boolean formulas (DQBF) | NEXP-complete problems | polynomial time (Karp) reductions | succinctly represented problems
Type
conference paper