https://scholars.lib.ntu.edu.tw/handle/123456789/632104
標題: | Dependency Stochastic Boolean Satisfiability: A Logical Formalism for NEXPTIME Decision Problems with Uncertainty | 作者: | Lee N.-Z JIE-HONG JIANG |
公開日期: | 2021 | 卷: | 5A | 起(迄)頁: | 3877-3885 | 來源出版物: | 35th AAAI Conference on Artificial Intelligence, AAAI 2021 | 摘要: | Stochastic Boolean Satisfiability (SSAT) is a logical formalism to model decision problems with uncertainty, such as Partially Observable Markov Decision Process (POMDP) for verification of probabilistic systems. SSAT, however, is limited by its descriptive power within the PSPACE complexity class. More complex problems, such as the NEXPTIME-complete Decentralized POMDP (Dec-POMDP), cannot be succinctly encoded with SSAT. To provide a logical formalism of such problems, we extend the Dependency Quantified Boolean Formula (DQBF), a representative problem in the NEXPTIME-complete class, to its stochastic variant, named Dependency SSAT (DSSAT), and show that DSSAT is also NEXPTIME-complete. We demonstrate the potential applications of DSSAT to circuit synthesis of probabilistic and approximate design. Furthermore, to study the descriptive power of DSSAT, we establish a polynomial-time reduction from Dec-POMDP to DSSAT. With the theoretical foundations paved in this work, we hope to encourage the development of DSSAT solvers for potential broad applications. Copyright © 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85129912790&partnerID=40&md5=ca9bf4ea1ead59a2a05319ad02727090 https://scholars.lib.ntu.edu.tw/handle/123456789/632104 |
SDG/關鍵字: | Artificial intelligence; Boolean algebra; Polynomial approximation; Stochastic models; Stochastic systems; Complexity class; Decentralised; Decision problems; Logical formalism; Modeling decisions; Partially observable Markov decision process; Power; Stochastic boolean satisfiability; Uncertainty; Verification of probabilistic systems; Markov processes |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。