Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a group and let O be a disklike G-transfer system. For transfers r,e∈O, write r<e when e restricts into r in the poset of restrictions, and write r<^S e and r<^F e when this restriction is respectively a compatibility success or…
Let F be the family of polynomial systems F such that Z(F) is finite and the Galois group of F over Q is dihedral or bicyclic. Let FEAS_C denote complex feasibility, namely the problem of deciding whether Z(F) is nonempty. Dihedral and…
Let a permutation perm be given together with positive integers numphase and numpile. In each of numphase rounds, the permutation may be shuffled using Dealer's choice on numpile piles, where the dealer chooses the pile assignment…
Let β≥ -1 and γ>0, and for n∈N set N=⌈ n/γ⌉. Under μ_0, draw z_1,…,z_N~ N(0,I_n) independently. Under μ_1, first draw u~U(±1^n), then, conditional on u, draw z_1,…,z_N~N(0,I_n+(β/n)uu^top). Denote these two distributions collectively by…
A constraint satisfaction problem (CSP) is a computational problem of deciding whether a finite set of variables can be assigned values from a finite domain so that all specified constraints are satisfied. A CSP has the ability to count…
For a graph G, let path-χ(G) denote its path-chromatic number. Path-chromatic two-colourability conjecture. It is NP-complete to decide if path-χ(G) leqslant 2. The source states this alongside the tree-chromatic claim, but does not…
Let G be a graph with maximum degree 4, and let T be a backbone tree. Write BBC_λ(G,T) for the minimum number of colors in a λ-backbone coloring. Extremal tree-coloring conjecture. There is no graph G with maximum degree 4 and no backbone…
Let D be a finite set of positive integers, and let χ(D) denote the chromatic number of the distance graph with distance set D. For a fixed integer k≥3, consider the decision problem of determining whether χ(D)≤ k. NP-completeness…
Let g(λ,μ,ν) denote Kronecker coefficients and c^α_βγ denote Littlewood–Richardson coefficients. Strong hardness conjecture. The Kronecker coefficients g(λ,μ,ν) and the Littlewood–Richardson coefficients c^α_βγ are strongly rm#P-hard. This…
Let T be a triangulation of a 3-manifold. Call the triangulated manifold small if it does not contain an incompressible surface of positive genus, and call it an integral homology sphere if it has the same integral homology as S^3. Suppose…
For a prime p, let F^*_n,n+1 denote the class of (n+1)-nomials in n variables, and let tt FEAS_Q_p be the feasibility problem for rational roots over the p-adic field Q_p. The p-adic NP-hardness conjecture. For any fixed prime p, tt…
Let Δ be a finitely bounded homogeneous structure, and let Γ be a finite-language reduct of Δ. The constraint satisfaction problem of Γ is denoted by CSP(Γ). Dichotomy conjecture. CSP(Γ) is either in P or NP-complete. Complete…
Consider the single-spike model with dimension p, sample size n, spike support size k, and signal strength β. Let z denote the sparse spike, and let p/n→ c. Polynomial-time support-recovery barrier conjecture. For fixed signal strength…
Let X be a hereditary subclass of bipartite permutation graphs. The induced subgraph isomorphism problem asks whether an input graph occurs as an induced subgraph of another input graph. Induced subgraph isomorphism hardness conjecture.…
Let M be a closed Riemannian 3-manifold. Ricci-flow simulation conjecture. Ricci flow with surgery on M can be accurately simulated in ER. In other words, Perelman's proof of geometrization should be placeable in ER; the paper gives no…
Consider a continuous random energy model (CREM) with concave covariance function A, inverse temperature β>β_c, tilde and ?, and ?. Let OPT=max_|v|=NX_v and let KL denote Kullback–Leibler divergence. Low-temperature algorithmic tradeoff…
Let G be a graph, let k be an integer, and let a numbering assign the integers 1,…,n distinctly to the vertices of G. A valid path is a 2-path whose middle vertex has a smaller number than both endpoints. MAX-VP completeness conjecture.…
Let (X,T) be an efficiently discretizable Morse–Smale dynamical system. A telic problem coming from the system is an associated decision problem, and P denotes the class of problems decidable in polynomial time. Morse–Smale tractability…
Let G be a graph, let S be a 3-subset of V(G), and let n=|V(G)|. For a set S, write ckappa(S) for the maximum number of internally disjoint trees connecting S. Li's conjecture. Given G, S, and an integer cell with 2≤ cell≤ n-2, deciding…
Let G be a graph and let k be a nonnegative integer. Consider the serial algorithm and parallel algorithm for constructing the k-skeleta of the clique complex of G described in the paper. Optimality conjecture. These algorithms are optimal…