Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let H be a d-regular multigraph on k vertices, and let ε>0. Write L_m(H) for an m-sheeted lift of H. The operators S_ε^rand, widetildeS_ε^rand, S_ε^adv, and widetildeS_ε^adv denote, respectively, random, respectful random, adversarial, and…
For some fixed positive integer n, let Δ⊂ R^n be a rational simplex. The simplex Polytope Translation hardness conjecture. For some fixed n, the Polytope Translation problem for rational simplices Δ⊂ R^n is NP-hard. This is proposed as a…
Let the uniform epimorphism problem ask, given a finitely presented group G and a finitely generated virtually abelian group H, whether there exists an epimorphism from G onto H. Friedl–Löh conjecture. The uniform epimorphism problem onto…
Let B be a reduct of a finitely bounded countable homogeneous structure. A primitive positive interpretation of a graph in B is an interpretation using primitive positive formulas, and a graph is homomorphically equivalent to K_3 when it…
Let H be a (not necessarily simple) graph. The involution-free reduction of H is the lexicographically minimal involution-free graph H' such that H→^* H'. The problem ⊕ HomsTo(H) asks for the number of graph homomorphisms to H, modulo 2.…
A knot diagram represents a knot, and its unknotting number is the minimum number of crossing changes required to transform it into the unknot. The associated decision problem asks, given a knot diagram and an integer n, whether the knot…
Let $\ruleset{Quantum Avoid True}$ be the quantum extension of the combinatorial game $\ruleset{Avoid True}$, and let a classical start mean that the initial position has no quantum superposition. Let $\ruleset{Quantum Nim}$ be the quantum…
Let M be a closed 3--manifold. Recognition conjecture. sc S^3 recognition lies in coNP. sc Lens space recognition lies in coNP. This proposes polynomially checkable certificates for recognizing when a closed 3--manifold is not the…
For a finite point set in the plane and a red-blue partition, the chromatic crossing number is the number of crossings between an edge of EMST(R) and an edge of EMST(B). The maximum chromatic crossing number is the largest such number over…
Let k be the clause width, let κ be the clause-density factor, and let Φ_k(n,m) denote a random k-SAT formula with n variables and m clauses. Let Theorem~ and Theorem~ denote the hardness results stated above. Low-degree polynomial…
Let H' be the set comprising H and other dense sets of true sentences unprovable in T, including the specified sets associated with universal Turing machines and Turing jumps. For a nondeterministic Turing machine M accepting coTHEOREMS,…
Let A be a reduct of a finitely bounded homogeneous structure. Let S be the finite structure defined by S:=(0,1;(0,0,1),(0,1,0),(1,0,0)). A structure is homomorphically equivalent to another when homomorphisms exist in both directions, and…
Let a_1,…,a_m∈Q^n and let ν∈[0,∞)∩Q. BoxContZonotope conjecture. Deciding whether there exists a rectangular box B such that ∑_j=1^m[-a_j,a_j]⊂ B, vol_n(B)≤ν is NP-hard. The problem is introduced as a further source of computational…
Let G be a graph with n vertices, and let k_1≥ 3 be fixed. For each k_1-subset S of V(G), let κ(S) be the maximum number of internally disjoint trees connecting S, and define κ_k_1(G)=minκ(S): S⊆ V(G), |S|=k_1. Let k be an integer…
Let k∈Z_+, let p∈(0,1)^k be a probability distribution, and let Q be a symmetric k× k matrix with nonnegative entries. Let P be the diagonal matrix with P_i,i=p_i, and let λ_1,λ_2 be the leading eigenvalues of PQ ordered by nonincreasing…
Let $Z$ be any instance of Nim, let $\phi\in{A,B,C,C',D}$ be a quantum flavor, and let $Z^{\mathrm{symBudgeted}[1]\mathcal Q(\phi,2)}$ denote the symmetric budgeted quantum game in which both players together can make at most one quantum…
A matroid M has branch-depth and c^*d^*-depth, two recursive depth parameters introduced in the paper. Computational hardness conjecture. Computing exactly the branch-depth and the c^*d^*-depth of matroids is NP-hard. The computational…
Let G be the graph input to the Pirates and Treasure game. A graph is cubic if every vertex has degree 3, and 3-connected if deleting fewer than three vertices does not disconnect it. Cubic or 3-connected hardness conjecture. Pirates and…
Let bT_δ be the noise operator that rewires ⌊δ n⌋ swaps of a d-regular graph, and let sG_n,d,k,η^ eq be the equitable stochastic block model. Write widetildesG^ eq_n,d,k,η,δ for the distribution of bT_δ(bG) when bG~sG_n,d,k,η^ eq. For…
Let A_1 and A_2 be countably infinite ω-categorical structures without algebraicity, not preserved by all permutations, and with the cross prevention property. A binary injective polymorphism is a binary operation preserving all relations…