Open problems in Algorithms & Simulation

On specific graph families, how close do learned or AI-generated heuristics get to exact optima for max-cut, vertex cover, and TSP variants — and where exactly do they fail?

Count the ways an n×m map can be folded flat along its creases — no closed form or polynomial algorithm is known even for 2×n — and decide which polyomino crease patterns fold into given 3D shapes.

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

Count self-avoiding walks of length n on a lattice and pin down the connective constant μ and critical exponents. On Z² the constant is unknown (≈ 2.638).

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