Research report
OpenAI publishes research-level First Proof submissions
OpenAI First Proof team · OpenAI internal reasoning model · ChatGPTRead report →
Open problems in theoretical computer science
A community-maintained index of formal questions, primary literature, downloadable research packs, and public reports of AI-assisted progress.
Archive contents
Open problems69 maintained recordsFormal statements and primary references.
Browse →Research packsFocused contextProblem TeX and its cited bibliography.
Learn more →Public reports3 artifact-backed reportsAttributable accounts of AI-assisted progress.
Read →Data catalogStatic JSON interfacesMachine-readable problem and report indexes.
Open data →Latest reports
Open problems
Design and analysis of algorithmsGraph algorithms analysis · Coloring great-circle arrangement graphs
3-Colorability of Arrangements of Great Circles
Determine whether the graph induced by any simple arrangement of great circles on the sphere is vertex 3-colorable.
Design and analysis of algorithmsGraph algorithms analysis · Low-bend orthogonal graph drawings
3D Minimum-Bend Orthogonal Graph Drawings
Determine whether every graph of maximum degree at most six has a crossing-free three-dimensional orthogonal drawing with at most two bends per edge.
Computational complexity and cryptographyProblems, reductions and completeness · Fine-grained complexity of 3SUM
3SUM Hard Problems
The 3SUM decision problem asks whether three integer sets contain elements a, b, and c satisfying a+b=c. The open question is whether 3SUM and the problems to which it reduces admit algorithms with a polynomial saving over quadratic time. Algorithms with logarithmic-factor improvements are known, but such an exponent saving is conjectured to be impossible even in expectation.
Randomness, geometry and discrete structuresPseudorandomness and derandomization · BPP derandomization
BPP versus P
Determine whether every bounded-error randomized polynomial-time algorithm can be replaced by a deterministic polynomial-time algorithm.
Randomness, geometry and discrete structuresComputational geometry · Unit-distance coloring of the plane
Chromatic Number of the Plane
Determine the minimum number of colors needed to color the Euclidean plane so that points at unit distance receive different colors.
Randomness, geometry and discrete structuresComputational geometry · Compatible point-set triangulations
Compatible Triangulations
Determine whether any two planar point sets of the same size and with the same number of hull vertices admit combinatorially compatible triangulations.