OpenTCSBrowse formal questions in theoretical computer science by field or keyword.
Determine whether the graph induced by any simple arrangement of great circles on the sphere is vertex 3-colorable.
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.
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.
Determine whether every bounded-error randomized polynomial-time algorithm can be replaced by a deterministic polynomial-time algorithm.
Determine the minimum number of colors needed to color the Euclidean plane so that points at unit distance receive different colors.
Determine whether any two planar point sets of the same size and with the same number of hull vertices admit combinatorially compatible triangulations.
For a polygon and a prescribed number of pieces, find mutually congruent pieces that leave the least uncovered area and characterize when a perfect congruent partition exists.
Determine the asymptotic growth constant and sharper enumeration bounds for fixed polyominoes of order n.
Determine tight extremal bounds for the number of unit-distance pairs and the minimum number of distinct distances among finite point sets in two and three dimensions.
Maintain a dynamic planar point set under insertions and deletions while supporting nearest-neighbor queries, with logarithmic time for every operation.
Determine the minimum number of colors required to color all edges of a complete geometric graph so that crossing edges receive different colors.
The open problem asks whether every convex polyhedron can be cut along its edges and unfolded into a single simple polygon in the plane without overlap. The answer is conjectured to be affirmative, but no general result is known.
Determine whether every genus-zero polycube can be cut along its unit-square edges and unfolded into one nonoverlapping planar piece.
For each integer k, identify or construct all polyhedra whose generic orthogonal projections always have exactly k sides.
The open problem asks whether the Euclidean minimum spanning tree of n points in R^d can be computed in time close to the (n n) lower bound. The difficulty is most pronounced in large dimension, where the reported upper bounds approach quadratic time.
Determine whether two dense square matrices over a field can be multiplied using essentially quadratic arithmetic operations.
Determine the minimum worst-case number of subdivision vertices needed to extend an arrangement of pseudosegments into a pseudoline arrangement.
Determine whether every convex polygon can be partitioned into any prescribed number of convex pieces having equal areas and equal perimeters.
The problem concerns the update-time complexity of computing the L_1 difference between two vectors specified by data streams. The standard approach described by the source uses projections onto pseudorandom vectors whose entries are drawn from the Cauchy distribution, but sufficient accuracy requires many independent inner products and can make each update costly. The open directions are to obtain faster L_1-difference algorithms through large-frequency or sparse-projection techniques and to prove nontrivial worst-case or amortized lower bounds for stream-update time.
For a finite point set in three-dimensional general position, determine whether all tetrahedralizations are connected by local bistellar flips.
Determine the computational complexity and approximability of awakening sleeping robots in metric and planar geometric spaces as quickly as possible.
Determine whether every closed nonconvex polyhedron has a connected cut set on its surface whose development is a single nonoverlapping planar polygon.
Determine whether graph isomorphism has a deterministic polynomial-time algorithm for arbitrary finite graphs.
Determine whether every convex three-dimensional polytope has a tetrahedralization whose dual graph contains a Hamiltonian path.
Given a set of points, a k-set is a subset of k points obtained by intersecting the point set with an open halfspace. The open problem is to determine the maximum possible number of k-sets. Even in two dimensions, the known upper and lower bounds remain separated.
Determine whether nondeterminism adds computational power when a machine is restricted to logarithmic working space.
The open problem is whether linear programming admits a strongly polynomial algorithm. Linear programming is known to be weakly polynomial, meaning polynomial in the bit complexity of the input, and strongly polynomial linear-time algorithms are known when the dimension is fixed.
Determine whether every planar graph has a crossing-free straight-line three-dimensional grid drawing of linear volume.
Determine the maximum number of lines tangent to four unit balls in three dimensions while avoiding the interiors of all other balls in the set.
For 2n points in the plane, the cost of a Euclidean matching is the total length of its edges. The open problem is to determine the computational complexity of finding a matching of minimum cost. An exact algorithm with running time O(n^1.5 ^5 n) is reported.
Determine whether a minimum-link path between two points in a planar polygonal domain can be computed in subquadratic time.
For a prescribed triangle, determine whether the plane admits a three-coloring containing no monochromatic congruent copy of that triangle.
Partition a square into finitely many pieces so as to minimize the maximum ratio of circumradius to inradius among the pieces.
For a set of n points in R^d whose convex hull has f faces, determine the optimal output-sensitive running time for constructing the hull.
Determine whether every decision problem whose solutions can be verified in polynomial time can also be solved in polynomial time.
Determine whether every problem solvable with polynomial working space is also solvable in polynomial time.
Determine the computational complexity of deciding how many congruent axis-parallel rectangles, with rotations allowed, fit in a larger rectangle.
Determine the computational complexity of finding a maximum-length traveling-salesperson tour through points in the Euclidean plane.
The open problem is to construct a linear-space data structure for point location in a three-dimensional subdivision that answers every query in logarithmic time. For a subdivision with n faces, the reported known result uses O(n n) space and answers queries in O( ^2 n) time.
Given a polygonal curve and an error tolerance, compute a simplification using the fewest original vertices and ask whether an optimal solution is possible in nearly linear time.
Given a triangulated surface in three dimensions and a tolerance, efficiently construct a simpler polyhedral surface within the prescribed error.
Determine whether every immersed spherical polyhedral surface made entirely of congruent regular pentagons is assembled from solid dodecahedra glued facet to facet.
Determine whether approximating the ground-state energy of a local quantum Hamiltonian remains QMA-hard at constant precision.
Determine whether planar graphs have queue number bounded by an absolute constant.
Determine whether a rectangle with rational side lengths can be tiled by finitely many rectangles of equal area whose perimeters are all distinct.
Determine the maximum, over planar point sets of size n, of the minimum number of reflex vertices in a polygonalization.
Determine the computational complexity of rolling a labeled die through every cell of a fully labeled rectangular board exactly once while matching each required top-face label.
A deterministic linear-time algorithm for triangulating a simple polygon is known, but its construction is intricate. The open problem is to find a deterministic linear-time triangulation algorithm that is significantly simpler. Randomization yields simpler algorithms, including one with linear running time.
Given a planar point set, count the simple polygons whose vertex set is exactly the given set, and determine whether this count can be computed in polynomial time.
Determine whether there are linear-size universal planar point sets on which every planar graph of a given order has a crossing-free straight-line drawing.
Given two sets of n real numbers, determine whether all n^2 pairwise sums can be sorted in optimal quadratic time.
Determine whether satisfiability for unbounded clause width fundamentally requires time approaching two to the number of variables.
Determine polynomial separation bounds, and hence efficient exact comparison methods, for differences between sums of square roots of bounded integers.
Prove that some language in NP requires Boolean circuits of superpolynomial size, equivalently that NP is not contained in P/poly.
Reconstruct a surface from a sufficiently dense point sample with a guarantee that the output is homeomorphic to the sampled surface, including surfaces with sharp edges and corners.
Determine whether every planar point set has at least as many pointed pseudotriangulations as triangulations, with equality only in convex position.
Determine whether every drawing of a graph in which each pair of edges meets exactly once has at most as many edges as vertices.
Determine whether every polygon can be transformed into a regular polygon by finitely many moves that send one vertex along its line to the centroid of the remaining vertices.
Determine whether a finite collection of pairwise disjoint planar segment mirrors can trap every ray emitted from a source point disjoint from the mirrors.
Determine the complexity of finding a shortest traveling-salesperson tour in a solid grid graph.
An object in three-dimensional space is called fat when the ratio of its circumradius to its inradius is bounded. The open problem is to determine the combinatorial complexity of the union of n such objects. This complexity is conjectured to be nearly quadratic in n.
Determine whether it is NP-hard to distinguish almost satisfiable unique constraint systems from instances in which only a small fraction can be satisfied.
Determine the worst-case number of inward-facing floodlights of aperture , placed at polygon vertices, that suffice to illuminate every simple polygon.
Determine whether every closed polyhedron can be cut along edges into a connected, nonoverlapping planar unfolding whose faces may remain joined only at vertices.
Determine the worst-case combinatorial complexity of the vertical decomposition of an arrangement of n constant-complexity surfaces in R^d for d 5.
Given a graph and a specified Hamiltonian cycle, determine whether they are respectively the visibility graph and boundary cycle of a simple polygon.
For a unit-area convex planar region, choose a perimeter-halving fold and maximize the volume enclosed after identifying the two boundary chains.
For a set of lines or line segments in three-dimensional space, the open question is to determine the combinatorial complexity of its Voronoi diagram. In the Euclidean case, the known lower bound is quadratic in the number of input objects, while the upper bound is essentially cubic. The complexity is conjectured to be nearly quadratic.
Determine whether the Yao-Yao geometric graph has bounded stretch for a fixed number of cones.
Determine whether every convex polyhedron can be cut open along a single vertex-spanning path and unfolded without overlap.