Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
Dependency Stochastic Boolean Satisfiability: A Logical Formalism for NEXPTIME Decision Problems with Uncertainty
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add randomized quantification and explicit dependencies for existential variables | DQBF, yielding DSSAT · DSSAT decision problem | complexity: NEXPTIME-complete | Helped |
| Encode a Dec-POMDP using DSSAT variables and dependency-constrained Skolem functions | Dec-POMDP · Finite-horizon Dec-POMDP | reduction | Helped |
| Encode probabilistic partial design equivalence checking as DSSAT | Probabilistic partial design · Probabilistic partial design equivalence checking | complexity characterization: NEXPTIME-complete | Helped |
| Represent approximate partial design with random input variables and no auxiliary error-triggering inputs | DSSAT · Approximate partial design | expressiveness | Helped |
Closest papers by meaning
- Lifting (D)QBF Preprocessing and Solving Techniques to (D)SSAT (AAAI 2023 · similarity 0.94)
- Unifying Decision and Function Queries in Stochastic Boolean Satisfiability (AAAI 2024 · similarity 0.93)
- A Sharp Leap from Quantified Boolean Formula to Stochastic Boolean Satisfiability Solving (AAAI 2021 · similarity 0.91)
- SharpSSAT: A Witness-Generating Stochastic Boolean Satisfiability Solver (AAAI 2023 · similarity 0.89)
- Solving Higher-Order Quantified Boolean Satisfiability via Higher-Order Model Checking (AAAI 2025 · similarity 0.84)
- Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.