https://scholars.lib.ntu.edu.tw/handle/123456789/634367
標題: | Reducing NEXP-complete problems to DQBF | 作者: | Chen, Fa Hsun Huang, Shen Chang Lu, Yu Cheng TONY TAN |
關鍵字: | Dependency quantified boolean formulas (DQBF) | NEXP-complete problems | polynomial time (Karp) reductions | succinctly represented problems | 公開日期: | 1-一月-2022 | 來源出版物: | Proceedings of the 22nd Conference on Formal Methods in Computer-Aided Design, FMCAD 2022 | 摘要: | 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. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/634367 | ISBN: | 9783854480532 | DOI: | 10.34727/2022/isbn.978-3-85448-053-2-26 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。