Tag · 5 problems · 4 fields

Open problems tagged sat

5 problems in the Math Lab index touch sat, spanning Algorithms & Simulation, Graph Theory, Combinatorics, Algebra. Each carries a precise statement, an honest status, and a computational line of attack.

Minimal superpermutations — extended searchAlgorithms & Simulationuntouched

Push the computational frontier on shortest superpermutations: close the 867–872 gap at n = 6 and improve constructions for n = 7–8.

No-three-in-line problemGraph Theoryuntouched

How many points can be placed in an n×n grid with no three collinear? At most 2n (two per row), and 2n is achieved for all n up to at least 46 — but conjecturally only ~1.814n is possible for large n.

Small hard CSP/SAT instancesAlgorithms & Simulationuntouched

Construct families of small constraint-satisfaction instances that are maximally hard for modern solvers, and extract minimal unsatisfiable cores that explain the hardness.

Van der Waerden numbersCombinatoricsuntouched

W(r, k) is the smallest N such that every r-coloring of 1…N contains a monochromatic k-term arithmetic progression. Only a handful of values are known exactly.

Williamson matricesAlgebrauntouched

For which odd n do Williamson matrices (four symmetric circulant ±1 matrices with A² + B² + C² + D² = 4nI) exist? Each solution yields a Hadamard matrix of order 4n.