Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For each fixed rational p∈(1,∞), given vectors v_1,…,v_m∈Q^d defining the zonotope Z=∑_i=1^mλ_i v_i: -1≤λ_i≤ 1, determine whether the optimization problem max_x∈ Z|x|_p is fixed-parameter tractable when parameterized by the dimension d;…
Let K_k and K_n be complete graphs, let E^r and E^g be precolored red and green edge sets, and let Ramsey(n,n) denote the classic symmetric binary Ramsey number. Classic Ramsey-number avoidance conjecture. Graph Ramsey avoidance games…
Fix a positive integer r. For a metric graph Γ=(G,l) with rational edge lengths, the r^th Metric Divisorial Gonality problem asks whether dgon_r(Γ)≤ k for a given integer k. Metric divisorial gonality conjecture. The r^th Metric Divisorial…
Let G be a bipartite graph, and let t denote the number of guards in the eternal domination game. The decision problem textscFast-Strategy asks whether the guards have a strategy satisfying the fast-winning condition on G. Fast-Strategy…
Conjecture: For every quantum polynomial-time sampler S and every classical string x that S outputs with probability δ, there is a quantum program for x of length at most log(1/δ)+O(log n), decodable in quantum polynomial time.…
For integers k,d, let GEM_k → d denote the decision problem of determining whether a given k-complex has a geometric embedding in R^d. Skopenkov's conjecture. The problem GEM_k → d is NP-hard for all k,d satisfying max3,k ≤ d ≤ 3/2k+1.…
A tournament is a directed graph in which exactly one of the two possible directions is chosen for every pair of distinct vertices. For a tournament T, its directed clique number overrightarrowω(T) is the minimum, over all linear orders ≪…
Let b be a braid with a fixed number of strands, let widehatb denote its closure, and let the number of crossings of b be the input size. Przytycki–Silvero conjecture. Computing the Khovanov homology Kh(widehatb) of a closed braid with…
Let H be a connected cubic graph. The H-problem asks, for a connected cubic graph G, whether G admits an H-coloring. Let C_NP be the class of connected cubic graphs H for which the H-problem is NP-complete. Hereditary-class conjecture. The…
Let P be a finite point set in the plane, and let cr-MST(P) denote its bicolored minimum spanning tree crossing number. The NP-hardness conjecture. Finding cr-MST(P) is NP-hard. This concerns the computational complexity of the bicolored…
Let A=[underlineA,overlineA]∈IR^n× n be an interval matrix, with midpoint Mid(A) and radius Rad(A), and let z^i=(1,…,1,-1,1,…,1)^T have -1 in the ith entry and 1 elsewhere. An interval matrix is an inverse M-matrix when it is nonsingular…
Let G be a graph, and let σ(G) denote the minimum number of equivalence relations needed to cover the line graph structure under the paper's definition. For an integer k≥ 3, the NP-completeness conjecture. It is NP-complete to decide…
For partitions λ,μ,ν, let ComputeLR be the problem whose input is λ,μ,ν encoded in unary and whose output is the Littlewood–Richardson coefficient c^λ_μν. Here unary encoding writes each part using a number of symbols proportional to its…
Let C be a natural complexity class, let h(L) denote the homological complexity of a problem L, and let S_C be a subset of N∪∞. Ultimate homological characterization. Every natural complexity class C can be characterized by C=L:h(L)∈ S_C…
Let d≥ 4, let λ_c(d) denote the critical fugacity for the hardcore model on the d-regular tree, and let λ satisfy λ_c(d)<λ. A fully polynomial approximation scheme (FPTAS) is an algorithm that approximates a partition function to arbitrary…
Let r≥ 3 be a rational number. For a graph G, let χ_c'(G) denote its circular chromatic index, and let CCHI^=_r be the decision problem of determining whether χ_c'(G)=r. DP-completeness conjecture. The problem CCHI^=_r is DP-complete. The…
Consider the step-wise odd-even algorithm depicted in Figure, and let N denote the number of elements being sorted. Its sequential worst-case runtime is compared with Bubble Sort, while parallelization executes the applicable row and…
A graph is IC-planar if it has a plane drawing in which no two crossings share an endpoint, and NIC-planar if it has a plane drawing in which any two crossings share at most one endpoint. NP-hardness conjecture. Testing whether a graph is…
Let H be a k-graph on n vertices, and let δ_ℓ(H) be its minimum ℓ-degree. Define bf PM(k,ℓ,δ) to be the decision problem of determining whether a k-graph on n vertices with minimum ℓ-degree at least δbinomnk-ℓ has a perfect matching; write…
Let f_i_i=1^k be a sequence of polynomials in P_n. The Hilbert Nullstellensatz decision problem over C asks whether these polynomials have a common zero in C^n. Smale's conjecture. There is no polynomial-time algorithm for deciding the…