Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let M( W) denote the Sherrington–Kirkpatrick Hamiltonian instance with random matrix W, and let c( W) be the approximation ratio certified by an algorithm. A certification algorithm runs in polynomial time if its running time is polynomial…
A tournament is a digraph obtained by orienting every edge of a complete graph, and a tournament is strong if it is strongly connected. A safe set is a vertex set satisfying the safe-set condition, and the associated decision problem asks…
Let P be a poset and let G_L(P) be its linear extension graph, whose vertices are the linear extensions of P. The dimension dim(P) is the minimum size of a realizer of P, that is, a set of linear extensions whose intersection is P.…
Let P_a and P_b be optimization problems such that one is the dual of the other, so that they exhibit strong duality. Strong-duality polynomial-solvability conjecture. Both P_a and P_b should be polynomially solvable. This conjecture is…
Let G be a finite graph and let H be a subgraph of G with at most k components, where k is a natural number. The notions S-Eulerian and semi S-Eulerian mean, respectively, that H has an S-Eulerian circuit or an S-Eulerian trail: a closed…
A quasigroup is an algebra whose multiplication table is a Latin square; equivalently, for all elements a,b, there are unique elements x,y such that ax=b and ya=b. The minimum generating set problem asks whether a given quasigroup has a…
Let QS5 be the quantified modal logic QS5, and consider its fragment using two individual variables and two unary predicate letters. Undecidability conjecture. The fragment of QS5 in the language with two individual variables and two unary…
Assume the setup of the paper's fl-RDT theorem, including the quantities ψ_rp, ψ_rd, hat p, hat q, and hat c. Define the algorithmically achievable value ψ_rp,a by ψ_rp,a=maxψ_rp | lim_n→∞P(ψ_rp can be achieved in polynomial time)=1. Let…
An odd hole is an induced cycle of odd length at least five. The odd-hole detection conjecture. It is NP-complete to determine whether a graph contains an odd hole. This conjecture concerns the complexity of odd-hole detection. The source…
Let t be a text permutation of length n, let π be a pattern permutation, and let σ be an arbitrary permutation of length O(1). Suppose that π avoids σ. Fixed-pattern avoidance conjecture. The permutation pattern matching problem with text…
Let Δ be an integer with Δ ≥ 3 and let β∈ C_A with β not ∈ R∪ i, -i. Let G be a graph with maximum degree at most Δ, and let Z_Ising(G; β) denote its Ising partition function. The approximation problems textscIsingNorm(β, Δ, 1.01) and…
Let G be a graph. It is 2-divisible if, for every induced subgraph H of G, the vertex set V(H) can be partitioned into sets A and B such that ω(A)<ω(H) and ω(B)<ω(H). The NP-completeness conjecture. It is NP-complete to determine whether a…
Let B be a first-order reduct of a finitely bounded homogeneous structure in a finite relational signature. The constraint satisfaction problem CSP(B) asks whether a finite input structure admits a homomorphism to B. Infinite-domain CSP…
Fix k greater than or equal to 1 and let a_n be the number of unlabeled k-regular graphs with n vertices. Regular-graph enumeration conjecture. The sequence a_n can be computed in polynomial time in n. The source notes polynomial…
A cubic graph is a graph in which every vertex has degree three. Mohar's conjecture. Approximating the genus of cubic graphs is APX-hard. This conjecture asserts computational hardness in the spherical-density regime, where graphs have…
Let T be a finite Γ-semiring, and consider the problem of deciding whether H^k_Γ(Spec_Γ(T), O_X)=0. Complexity conjecture. This problem lies in coNP, and becomes P-complete for cyclic additive semirings. The claim gives a proposed…
The Builder-Blocker general position games are played on a graph, with Builder and Blocker alternately selecting vertices according to the rules defining the games; the associated decision problems ask whether Builder has a winning…
Let A be a finite domain, let Γ be a constraint language on A, and let QCSP(Γ) denote the quantified constraint satisfaction problem for Γ. A mighty tuple II is the structural configuration defined in the paper, and a constraint language…
Let P_n and Q_n be probability distributions on Ω_n, with likelihood ratio L_n=dP_n/dQ_n. For a degree bound D, let L_n^≤ D denote the orthogonal projection of L_n onto the degree-D polynomials under the L^2(Q_n) inner product. Informal…
Let k≥ 4 be fixed, and let G be a graph with maximal local edge-connectivity k, meaning that the maximum local edge-connectivity over all pairs of vertices of G is k. A k-colouring of G is a proper vertex colouring using at most k colours.…