-
Notifications
You must be signed in to change notification settings - Fork 4
Description
Problem
Two implemented problems use dims() = vec![] and perform the entire computation inside evaluate():
QuantifiedBooleanFormulas(src/models/formula/qbf.rs) — PSPACE-complete.evaluate(&[])runs a full O(2^n) game-tree search internally.GeneralizedHex(src/models/graph/generalized_hex.rs) — PSPACE-complete.evaluate(&[])runs minimax with memoization internally.
This pattern has several issues:
1. Semantic mismatch with the Problem trait
The Problem trait is designed so that:
dims()defines the search space (e.g.,[2, 2, 2]= 3 binary variables)evaluate(config)evaluates a single configuration from that search space- Solvers (BruteForce, ILP) enumerate/optimize over configurations
With dims() = vec![], there is exactly one "configuration" (the empty slice), so find_satisfying() simply calls evaluate(&[]) once. The entire exponential-time computation is hidden inside evaluate, and the solver framework adds no value.
2. Brute-force solver is meaningless
BruteForce::find_satisfying() on these problems either returns Some(vec![]) or None — there's no search, no enumeration, no optimization. The solver is just a wrapper around a single function call.
3. Same class as Network Reliability / Network Survivability
Issues #235 (NetworkReliability) and #237 (NetworkSurvivability) were put on hold because their GJ decision questions require aggregating over all configurations (probability computation), which doesn't fit evaluate(single_config) -> bool. The dims()=vec![] pattern is another manifestation of the same underlying issue: problems where the "answer" is not a property of any individual configuration but of the entire configuration space.
Affected problems
| Problem | Complexity class | evaluate does |
|---|---|---|
QuantifiedBooleanFormulas |
PSPACE-complete | O(2^n) game-tree search |
GeneralizedHex |
PSPACE-complete | O(3^n) minimax search |
| NetworkReliability (#235) | #P-hard | Would need O(2^m) weighted sum |
| NetworkSurvivability (#237) | #P-hard | Would need O(2^(n+m)) weighted sum |
Questions to resolve
- Should we support problems beyond NP (PSPACE, #P) in the trait system?
- If yes, should there be a separate trait (e.g.,
PspaceProblem,CountingProblem) with different solver semantics? - If no, should QBF and GeneralizedHex be removed or redesigned?
- Is it acceptable for
evaluate()to take exponential time, or should it always be polynomial in the input size?
Related issues
- [Model] NetworkReliability #235 — [Model] NetworkReliability (On Hold)
- [Model] NetworkSurvivability #237 — [Model] NetworkSurvivability (On Hold)
- [Rule] STEINER TREE to NETWORK RELIABILITY #256 — [Rule] STEINER TREE to NETWORK RELIABILITY (On Hold)
- [Rule] VERTEX COVER to NETWORK SURVIVABILITY #257 — [Rule] VERTEX COVER to NETWORK SURVIVABILITY (On Hold)