Are the Probabilities the Incompressible Part of Stochastic Planning?

Planning under uncertainty can be written as a logic puzzle. Stochastic satisfiability (SSAT) is a Boolean formula in which some variables are chosen by the planner and others are coin flips with stated probabilities. The question is whether the planner can make the formula true with probability at least some threshold. Preprocessing theory asks whether such inputs can always be shrunk, in polynomial time, to an equivalent input whose size depends only on a small structural measure. Shrinkage of that kind is called a polynomial kernel. The standard tool for proving it impossible is cross-composition: a construction that packs many independent hard instances into one instance without increasing the structural measure.

This note asks one sharp question. The deterministic analogues, propositional satisfiability (SAT) and quantified Boolean formulas (QBF), restricted to three literals per clause, trivially shrink to size cubic in the number of variables $n$, because there are at most about $n^3$ distinct clauses. SSAT keeps the same clauses but adds coin-flip probabilities and a threshold, all written as rational numbers of arbitrary bit length. So the only thing that could make bounded-width SSAT incompressible is the numbers. We propose either to prove a cross-composition that hides many hard instances inside those probability bits, or to give a sound rounding procedure that cuts every probability to $\mathrm{poly}(n)$ bits without changing any threshold decision. We then test the practical side of whichever answer holds on the published SSAT and POMDP-derived suites.

Core Claim

Fix an SSAT formula $\Phi$ over $n$ variables in 3-CNF (a conjunction of clauses with at most three literals each), with a quantifier prefix that mixes planner-chosen variables and randomized variables. Each randomized variable $v$ is true with a given rational probability $p_v$. Let $P(\Phi)$ be its maximum satisfaction probability: take the maximum over planner choices and the probability-weighted average over coin flips, in prefix order. The decision problem is

$$\text{given } (\Phi, (p_v)_v, \theta), \text{ decide whether } P(\Phi) \ge \theta,$$

parameterized by $n$. It is fixed-parameter tractable, since exhaustive evaluation takes $2^n$ times a polynomial in the input length. Its deterministic restriction (all variables planner-chosen or universally quantified) has a trivial polynomial kernel. Whether the weighted problem has one is open, and the open part is entirely about chance.

We call this chance-attributable incompressibility: kernel lower bounds that hold for the stochastic problem under a parameter where the deterministic problem provably compresses. Our hypothesis is that such a lower bound exists for exact thresholds, under the standard assumption $\mathrm{NP} \not\subseteq \mathrm{coNP/poly}$. If true, it would be the first formal version of the observation that coin-flip variables carry weight that preprocessing cannot discard. The competing hypothesis is also worth establishing. Under it, a sign-preserving rounding scheme compresses $(p, \theta)$ to $\mathrm{poly}(n)$ bits, and that would be a preprocessing rule with a guarantee for exact SSAT solvers and checkers.

Why existing results do not settle it

Several papers motivate the question without answering it.

Cheng and Jiang lift QBF preprocessing to dependency-SSAT in Lifting (D)QBF Preprocessing and Solving Techniques to (D)SSAT. They prove that universal reduction, the QBF rule that deletes universal literals from clauses, is unsound once those variables carry probabilities. That is a statement about one rule. Our question is whether every polynomial-time shrinking procedure must fail.

Szeider's Limits of Preprocessing and Bäckström et al.'s Parameterized Complexity and Kernel Bounds for Hard Planning Problems prove no-polynomial-kernel results for SAT under backdoor parameters, for CSP under treewidth, and for NP-hard fragments of deterministic planning under plan length. Both papers constrain the design of this project. Every lower bound they give transfers to SSAT for free, by setting all probabilities to 0 or 1. That transfer is exactly why the obvious extension, "SSAT planning has no polynomial kernel under horizon or plan length," is not worth proposing: it is a corollary of the deterministic result. We therefore restrict attention to a parameter where the deterministic problem compresses, so that any lower bound has to come from the probabilities.

A planning-native candidate shows how easy it is to fall into the transfer trap. Take Bäckström et al.'s zero-precondition, single-effect fragment, which is polynomial deterministically, and make each effect stochastic. A short calculation suggests it stays polynomial. The goal fluents decouple, and the per-fluent success probability $1-(1-p)^j$ after $j$ attempts is log-concave in $j$, so a greedy allocation of the step budget appears optimal. That calculation still has to be checked. If it holds, chance does not hurt there either, and the numeric parameterization is the cleaner target.

Lokshtanov et al.'s Kernelization of Counting Problems supplies method. It defines compressions for counting problems as a reduce step followed by a lift step, and introduces SUM- and EXACT-cross-composition, with lower bounds resting on an unproven SUM-conjecture. Their constructions combine graph instances. Ours must combine instances inside numbers while keeping the clause structure fixed, and it targets the threshold decision problem under the classical hypothesis rather than the SUM-conjecture.

Finally, On the Relationship Between Satisfiability and Markov Decision Processes and Planning under Uncertainty via Stochastic Satisfiability are why the parameterization matters for planning. The first gives polynomial translations between finite-horizon POMDPs (partially observable Markov decision processes) and SSAT. The second encodes probabilistic plans as SSAT. In both, transition and observation probabilities become the $p_v$, so the numbers we study are the model's dynamics.

Research Program

The theoretical core has two arms pursued in parallel. Whichever closes first determines the paper.

The lower-bound arm builds a numeric OR-cross-composition. It is a polynomial-time map from $t$ instances of an NP-hard source problem to one 3-CNF SSAT instance with $n = \mathrm{poly}(s) + O(\log t)$ variables, where $s$ is the size of one source instance. The answer must be yes exactly when some source instance is yes. Because 3-CNF caps the number of distinct clauses at $O(n^3)$, the selector cannot be the usual long clause "$\text{selector} \ne i \ \vee\ C$". Each source's information must instead be written into the bits of the $p_v$ and $\theta$.

The design we will pursue has three parts. Planner variables encode a pair (instance index, candidate witness). For each such choice, the satisfaction probability is a multilinear polynomial in the $p_v$ with small integer coefficients. The $p_v$ are chosen as sums of widely separated powers of two, so that distinct bit blocks of that polynomial's value spell out whether the chosen witness is valid for the chosen instance. This resembles digit-packing reductions for subset-sum-like problems.

The key technical risk is carries between bit blocks. Multilinear products mix the blocks, and controlling that mixing with only $O(\log t)$ extra variables is the whole difficulty.

The upper-bound arm studies sign-preserving rounding. $P(\Phi)$ is a piecewise multilinear function of the probabilities: maximization over planner choices selects among $2^{O(n)}$ polynomials of degree at most $n$. The answer depends only on which sign region of these polynomials, and of their differences with $\theta$, the point $(p,\theta)$ lies in. We will ask whether every such region contains a rational point with $\mathrm{poly}(n)$-bit coordinates. Generic bounds from real algebraic geometry give bit sizes exponential in the number of variables. That is consistent with a lower bound but does not prove one. Multilinearity together with the restricted coefficient structure may allow a polynomial bound.

A clean intermediate result is also available. The promise version, which only guarantees correct answers when $|P(\Phi)-\theta| \ge \varepsilon$, compresses trivially to $O(n\log(1/\varepsilon))$ bits by rounding. So the open problem is exactly the exact-threshold case. We will state that dichotomy formally.

The empirical arm turns whichever answer we reach into a concrete preprocessing step, called certified probability rounding. It rounds each $p_v$ and $\theta$ to $b$ bits. It then decides the rounded instance and re-checks with interval arithmetic, increasing $b$ until the interval for $P(\Phi)$ excludes $\theta$. The result is a sound reduced instance plus the number of bits actually needed. On real suites this measures how much information the probabilities carry in practice, and it gives exact solvers smaller numbers to work with.

Baselines

The naive reference point is no numeric preprocessing: exact solvers run on the original rational probabilities. As the solver we use SharpSSAT from SharpSSAT: A Witness-Generating Stochastic Boolean Satisfiability Solver. That paper reports it solving 232 of 357 instances in its multi-family suite, ahead of ElimSSAT (226), ClauSSat (196), Prime (186) and DC-SSAT (177). Beating it means preserving every decision while lowering runtime or memory on that suite under the same time and memory limits.

The strongest existing preprocessor is DSSATpre from Lifting (D)QBF Preprocessing and Solving Techniques to (D)SSAT. It reports a 25.5% reduction in PAR2 for DC-SSAT on 2,316 instances adapted from DQBF benchmarks, with 30 instances solved during preprocessing alone. DSSATpre simplifies clauses but leaves probability values as they are, so the fair comparison is DSSATpre alone versus DSSATpre followed by certified rounding, with the same downstream solver and limits. Beating it means a further PAR2 reduction on suites with nontrivial probabilities. That suite maps every universal variable to probability 0.5, so the numbers carry no information there. We therefore expect no gain on it and use it as a negative control.

The obvious engineering competitor is fixed-precision floating-point evaluation, for example 64-bit doubles. We run it on identical instances and count threshold decisions that flip relative to exact arithmetic. Our method beats it if it matches doubles' speed while producing zero flips.

The ablation that isolates the key ingredient is rounding without the interval re-check, at the same bit budget $b$. It shows how often the certification step is what prevents wrong answers.

For compiled representations, we compare against levelized dec-DNNF (a decision-graph form whose node order follows the quantifier prefix) from Knowledge Compilation for Incremental and Checkable Stochastic Boolean Satisfiability. That paper reports reweighting queries at about 9.3% of compilation time and break-even after 1.5 queries on average. Reweighting is exactly the operation whose exact-arithmetic cost depends on probability bit length. For the effect of probability bit length on any of these solvers: no reported result found on Lacuna.

Why not just…?

Why not just inherit lower bounds from SAT, counting, or deterministic planning? Setting probabilities to 0 or 1 transfers every bound in Limits of Preprocessing and Parameterized Complexity and Kernel Bounds for Hard Planning Problems. Making all variables randomized connects SSAT to the counting bounds in Kernelization of Counting Problems. None of these says anything about 3-CNF SSAT parameterized by $n$, because there the deterministic and counting-free versions compress in cubic size. That gap is the reason for choosing this parameter. If our lower-bound arm fails and rounding succeeds, the honest conclusion is that chance adds no incompressibility under this parameter, and we will report it that way.

Why not just use double-precision floats? For most instances this will work. The real question is how often benchmark instances sit close enough to their threshold that a rounding error flips the answer. Nested threshold queries in Unifying Decision and Function Queries in Stochastic Boolean Satisfiability compound rounding errors across levels, and certified checking in cert-SSAT requires exact values. The flip-count experiment settles it. If doubles never flip on any suite, including the threshold-quantified Crowds and stracomp families, the practical contribution shrinks to a guarantee, and we will say so.

Why not just solve the promise (gap) version, which compresses trivially? This is a real threat to the practical motivation, though not to the theoretical question. The experiments therefore report the empirical distribution of $|P(\Phi)-\theta|$ across suites. If the gap is almost always large, gap compression is the right engineering answer, and exactness matters only for verification and for nested thresholds.

Proposed Experiments

The first decisive check is theoretical and is judged by whether a proof closes. On the lower-bound side we need a numeric composition for 3-CNF SSAT whose variable count is independent of $t$ up to $O(\log t)$. On the upper-bound side we need a $\mathrm{poly}(n)$-bit sign-preserving rounding. Either result answers the core question. Before attempting the general construction, we will try the carry-control gadget on randomized-only prefixes, where the satisfaction probability is a single multilinear polynomial.

The empirical checks use the 357-instance SharpSSAT suite, the 236-instance ClauSSat suite from Knowledge Compilation for Incremental and Checkable Stochastic Boolean Satisfiability, the Crowds and modified tlc/gttt/Robot/stracomp families from Unifying Decision and Function Queries in Stochastic Boolean Satisfiability, and the 13 POMDP benchmarks (tiger, aloha, hallway and others) encoded via On the Relationship Between Satisfiability and Markov Decision Processes. The DQBF-derived suite serves as the uniform-0.5 control. For each instance we record five measurements: the minimal certified bit budget $b^*$ relative to $n$, the threshold gap, decision flips under doubles, end-to-end runtime and memory with and without rounding, and levelized dec-DNNF reweighting time as a function of $b$.

The result that would most strengthen the lower-bound hypothesis is $b^*$ growing much faster than $n$ on structured families. The second probe applies the same measurement to synthetic instances produced by our composition, if it exists. The result that would favour the upper-bound arm is $b^*$ staying within a small polynomial of $n$ on every family, including instances generated adversarially near threshold.