Problem dossier · Algorithms & Simulation
Small hard CSP/SAT instances
Construct families of small constraint-satisfaction instances that are maximally hard for modern solvers, and extract minimal unsatisfiable cores that explain the hardness.
§1
Status
Open-ended engineering/science frontier tied to proof complexity: resolution lower bounds predict hardness, but the map from structure to solver pain is poorly charted.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Generate instances near phase transitions and adversarially tune them against CDCL solvers; minimize unsat cores automatically; correlate hardness with proof-complexity measures.
Tags: sat · csp · phase transition · proof complexity
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Algorithms & Simulation and adjacent territory.
- Heuristics vs. exact methods on NP-hard problems — Algorithms & Simulation
- Map folding & polyomino folding — Algorithms & Simulation
- Minimal superpermutations — extended search — Algorithms & Simulation
- Self-avoiding walks — Algorithms & Simulation
- No-three-in-line problem — Graph Theory
- Van der Waerden numbers — Combinatorics