OP-10043Computational complexityStatus unassessed
Polynomial-time computability of factoring
Polynomial-time computability of factoring
Formal Conjectures· Specialist source · status unassessed
The index
Computer science
285 entries matching the current filters. Sorted by recently added.
OP-9980Computational complexityStatus unassessed
Černý Conjecture
Černý Conjecture
Formal Conjectures· Specialist source · status unassessed
OP-9955Computational complexityStatus unassessed
Strong Sensitivity Conjecture (`bs(f) ≤ s(f)^2`)
Strong Sensitivity Conjecture ( bs(f) ≤ s(f)^2 )
Formal Conjectures· Specialist source · status unassessed
OP-9762Computational complexityStatus unassessed
Conjectures in Complexity Theory
Conjectures in Complexity Theory
Formal Conjectures· Specialist source · status unassessed
OP-9555Computational geometryStatus unassessed
Zipper unfoldings of convex polyhedra
Can every convex polyhedron be flattened without overlap after cutting along one simple path through all its vertices? This zipper path may traverse face interiors, and is not required to follow the edge graph.
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9554Computational geometryStatus unassessed
Constructive classification of equiprojective polyhedra
For each k , classify or construct all k -equiprojective polyhedra: polyhedra whose orthogonal projection is a k -gon in every direction not parallel to a face. The source already gives an edge-face-pair…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9553Computational geometryStatus unassessed
Coloring geometric complete graphs into noncrossing classes
For a general-position set of n planar points, color every segment joining two points so that properly crossing segments have different colors. Determine the worst-case minimum number of colors as a function of n ;…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9552Computational geometryStatus unassessed
Spherical polyhedral surfaces made of regular pentagons
Must every closed polyhedral surface homeomorphic to S^2 , composed of congruent regular pentagons and immersed in mathbb R ^3 , arise as the boundary of a union of solid regular dodecahedra joined along whole faces?
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9551Computational geometryStatus unassessed
Rolling a die over a fully labeled rectangular board
A rectangular grid board assigns a value from one to six to every cell. Determine the complexity of deciding whether a standard labeled die, from the specified corner and initial orientation, can roll across the board…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9550Computational geometryStatus unassessed
Worst-case reflexivity of planar point sets
For a planar point set S in general position, let rho(S) be the minimum number of reflex vertices in a simple polygon using exactly S as its vertices. Determine rho(n)= max |S|=n rho(S) . Is rho(n)= lfloor n/4 rfloor ?
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9549Computational geometryStatus unassessed
Edge unfoldings of genus-zero polycubes
Can every genus-zero polyhedron formed by joining unit cubes face to face be unfolded into one planar piece without overlap by cutting along exposed cube edges? All cube edges on the boundary are available, including…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9548Computational geometryStatus unassessed
Logarithmic dynamic nearest-neighbor queries in the plane
Can a data structure maintain n planar points under insertion and deletion, and return the Euclidean nearest neighbor of any query point, with O( log n) time for each operation? Specify whether update guarantees are…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9547Computational geometryStatus unassessed
Maximum volume from a perimeter-halving fold
Among convex planar shapes of unit area, which yields the largest volume by perimeter-halving folding? Choose two boundary points that divide the perimeter equally and identify the two intervening boundary arcs by equal…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9546Computational geometryStatus unassessed
Optimal circularity of convex partitions of a square
For a convex piece, define circularity as its smallest enclosing-circle radius divided by its largest inscribed-circle radius. Determine the infimum, over finite convex polygonal partitions of a square, of the largest…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9545Computational geometryStatus unassessed
Three-colorings avoiding a prescribed monochromatic triangle
For each fixed nondegenerate planar triangle, does there exist a three-coloring of the entire plane with no congruent copy whose three vertices all have one color? The coloring may depend on the chosen triangle, and…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9544Computational geometryStatus unassessed
Complexity of rectangular pallet loading
Given positive integer dimensions A,B,a,b and an integer n in binary, decide whether n interior-disjoint a times b rectangles fit inside an A times B rectangle. Each small rectangle may use either axis-parallel…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9543Computational geometryStatus unassessed
Shortest traveling-salesman tours in solid grid graphs
Determine the complexity of a shortest closed walk visiting every vertex of a solid planar grid graph. Vertices are lattice points, all unit-distance edges are included, the graph has no holes, and lengths are measured…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9542Computational geometryStatus unassessed
Complexity of the planar Euclidean maximum traveling salesman problem
Determine the computational complexity of finding a Hamiltonian tour of maximum total Euclidean length through a given finite set of planar points. The metric is ordinary Euclidean distance, and the objective is to…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9541Computational geometryStatus unassessed
Two-bend orthogonal drawings of degree-six graphs
Does every finite simple graph of maximum degree at most six admit a drawing with vertices on mathbb Z ^3 and edges following axis-parallel lattice paths with at most two bends each? Distinct paths may meet only at a…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9540Computational geometryStatus unassessed
Smallest universal point sets for planar graph drawings
Determine the minimum size u(n) of a planar point set on which every n -vertex planar graph has a crossing-free straight-line drawing, using a subset of the points as its vertices. In particular, is u(n)=O(n) possible?
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9539Computational geometryStatus unassessed
General unfoldings of nonconvex polyhedra
Can the surface of every closed nonconvex polyhedron be cut into a single connected piece that flattens into the plane without overlap? Cuts may cross face interiors, so they need not follow the original edges.
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9538Computational geometryStatus unassessed
Vertex unfoldings of polyhedra with nonsimplicial faces
Does every closed polyhedron with simply connected faces admit a nonoverlapping planar unfolding obtained by cutting edges while retaining enough vertex contacts to keep all faces in one connected piece? Faces must…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9537Computational geometryStatus unassessed
Optimal time to sort all pairwise sums
Given two lists X and Y of n real numbers each, determine the optimal running time for outputting the n^2 sums x+y in sorted order. Can the additive structure yield an O(n^2) -time algorithm in the standard…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9536Computational geometryStatus unassessed
Comparing counts of triangulations and pointed pseudotriangulations
For a planar point set, is the number of pointed pseudotriangulations at least the number of triangulations, with equality only for convex position? A pseudotriangulation partitions its convex hull into polygons with…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
OP-9535Computational geometryStatus unassessed
Compatible triangulations of two planar point sets
Do any two general-position planar point sets with the same cardinality and the same number of convex-hull vertices have triangulations with isomorphic face lattices? The bijection between the two vertex sets may be…
The Open Problems Project (computational geometry)· Research-list selection · status unassessed
Frequent tags
theoremdb 3909historical workshop 3469aim 3469icm 2898source curated 2675source candidate 1231number theory 1007status unassessed 622specialist collection 522pde dyn 399geometry 336analysis 269algebraic geometry 257algebra 224verifiable 2026 223probability 221graph theory 200topology 199lie rep 180combinatorics 154combinatorics discrete mathematics 141mathematical physics mechanics 137numerical analysis computer science 131research 2026 126