Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A map is a 2-cell decomposition of a closed compact surface, and its size is measured by n, the number of darts. Two maps are isomorphic when there is a bijection preserving their vertex-edge-face incidences. The genus is unrestricted when…
Let α be a non-quadratic scalar. Undecidability conjecture. α-Presburger arithmetic sentences with three alternating blocks of quantifiers are undecidable. The paper contrasts this with the known complexity results for one and three…
For a point set in Euclidean space, the k-MAX-EMST-ratio problem restricts the input to k dimensions. Fixed-dimensional hardness conjecture. The k-MAX-EMST-ratio problem for k∈2,3 is NP-hard. The unrestricted MAX-EMST-ratio problem is…
A generator is a map g:0,1^*→0,1^* whose restriction to inputs of length n maps into strings of length m(n)>n and is computed by circuits of size polynomial in m(n). For a propositional proof system P, let bf s_P(φ) denote the minimum…
Let b4∈[0,1], let k≥ 2, and let ℓ∈[k-1]. Define PM(k,ℓ,δ) to be the problem of deciding whether a k-graph on n vertices with minimum ℓ-degree at least δbinomnk-ℓ has a perfect matching. The polynomial-time threshold conjecture. PM(k,ℓ,δ)…
Let BestStep denote the problem of computing an optimal next step for the online covering problem for the time-dependent biased random walk on a graph. BestStep hardness conjecture. For undirected graphs, BestStep is PSPACE-hard. The paper…
For each positive integer n, consider the finite set of core trees with n vertices, meaning oriented trees whose only endomorphisms are automorphisms. Let the fraction of these trees that are NL-hard be measured uniformly. Asymptotic…
Let H be a finite structure with finite relational signature, and let its polymorphisms be the edge-preserving operations on its domain. A Kearnes–Kiss chain is the chain defined in Section~. Larose–Tesson's conjecture. If the…
Let A be a finite algebra, and say that it has few subpowers when the equivalent conditions in the source's Few Subpowers theorem hold. Given a finite subset S⊆ A^n and an element x∈ A^n, the subpower membership problem asks whether x…
Let cal A be a circuit architecture, and let cal H_cal A be the distribution of circuits in cal A whose gates are independently drawn from Haar measure. Random circuit sampling (RCS) is the task of receiving a circuit C sampled from cal…
Let bf J=(J_ij:1leqslant i<jleqslant n)∈R^n(n-1)/2 have independent and identically distributed entries J_ijstackreld=N(0,1). Let widehatZ(bf J) denote the target approximation to the partition function, and let an oracle O(·) operate in a…
Let Bayesian A-optimal design (Bayesian AOD) denote the problem of selecting a subset of design vectors to minimize the regularized trace objective f(S):=tr((∑_i∈ S a_i a_i^top+λ I_d)^-1). Hendrych's NP-hardness conjecture. The Bayesian…
Let A be a reduct of a finitely bounded homogeneous structure: it is obtained by forgetting some relations from a homogeneous structure, and the ambient structure is characterized among finite structures by forbidding embeddings of a…
Let G be a graph and let (α,β) be a pair of integers with maxα,β>1. An (α,β)-modular decomposition is a modular decomposition of G with parameters (α,β). NP-completeness conjecture. For every (α,β) with maxα,β>1, finding an (α,β)-modular…
Let X^α be an r-fold cover of a graph X, where ξ(X^α,t) is the transversal polynomial and deg(ξ(X^α,t)) is the maximum number of edges satisfied by a labelling of X. For all ε,δ>0, there exists r=r(ε,δ) such that, given an r-fold cover X^α…
For a poset P, its sign imbalance is the absolute difference between the numbers of even and odd linear extensions. The computational problem Sign Imbalance takes a poset P as input and outputs its sign imbalance; the class #P consists of…
Let S_w denote the Schubert polynomial indexed by w∈ S_∞, and define c^w_u,v by S_uS_v=∑_w∈ S_∞c^w_u,vS_w. Writing sc_Schubert for the function computing these coefficients, Schubert non-membership conjecture. sc_Schubert is not in #P.…
An extensional ESO sentence Φ defines a decision problem by asking whether the sentence holds on the input structure. Extensional ESO NP-intermediate conjecture. There is an extensional ESO sentence Φ such that deciding Φ is…
Let A be an integer matrix with columns v_1,…, v_n∈Z^m, let C=μ_1 v_1+…+μ_n v_n:μ_1,…,μ_n≥ 0, and set v= v_1+…+ v_n. Let P(A, b) denote the integer knapsack polytope, and let g(A) be the diagonal Frobenius number, namely the minimal s≥ 0…
Let H be a connected cubic graph, and consider the decision problem that asks, for a connected cubic graph G, whether G admits an H-coloring. P_12 dichotomy conjecture. If H admits a P_12-coloring, then the H-problem is NP-complete; if H…