Tag · 4 problems · 4 fields

Open problems tagged search

4 problems in the Math Lab index touch search, spanning Algorithms & Simulation, Graph Theory, Number Theory, Combinatorics. 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.

Perfect cuboidNumber Theoryuntouched

Does a rectangular box exist whose three edges, three face diagonals, and space diagonal are all integers? Euler bricks (integer edges and face diagonals) exist; adding the space diagonal is the open part.

a.k.a. Euler brick with integer space diagonal

Superpermutation problemCombinatoricsuntouched

What is the shortest string over n symbols containing every permutation of them as a consecutive substring? Known exactly only for n ≤ 5.