Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
A polyomino is a finite union of edge-connected unit squares in the plane. It is row-convex if each row has at most one connected component, column-convex if each column has at most one connected component, and convex if it is both…
Let H be a connected directed graph in which every vertex has positive indegree and outdegree. Let the core of H mean its core under directed graph homomorphisms. Bang-Jensen–Hell conjecture. If the core of H is a directed cycle, then the…
Let G~G_d(N,κ,q_1,q_2) be a hypergraphic planted dense subgraph with q_1>q_2, adjacency tensor mathbfcal A, and recovery error E_rm HPDS_R. HPDS recovery conjecture. If liminf_N→∞log_Nκ≥frac12 and…
Let MOTJ denote the problem of deciding, for an undirected graph G=(V,E) with rational edge weights w:E→Q, a set T⊆ V, and k∈Q, whether there is an odd T-join of total weight at most k. Let SOC denote the corresponding problem of finding a…
Let ε>0, and consider the decision problem of completing an arbitrary ε-dense partial Latin square, where an n× n partial Latin square is ε-dense if each symbol, row, and column contains at most ε n nonblank cells. NP-completeness…
Let H be an order-K hypergraph in the HPC detection problem, with null distribution H_0:H~H_K(p,1/2) and planted-clique alternative H_1:H~H_K(p,1/2,κ_p), where κ_p satisfies limsup_p→∞fraclogκ_plog√p≤ 1-τ. A polynomial-time test is a…
Let O be the origin in Z^2, and let a_n be the number of self-avoiding walks from O to O of length n. A Wilfian formula of type (W1) is an algorithm computing a_n in time polynomial in n. Self-avoiding-walk Wilfian conjecture. The sequence…
For integers 2≤ k<l, let LO_k and LO_l denote the corresponding symmetric relational templates, and let PCSP(LO_k,LO_l) be the promise problem whose instances homomorphically map to LO_k and whose outputs must homomorphically map to LO_l.…
Let G be a graph and let k∈N. The on-line chromatic number conjecture. Deciding whether χ^O(G)≤ k is \textsc{PSPACE}-complete. The complexity of deciding whether the on-line chromatic number satisfies this bound was open in the paper; it…
A cubic graph is a graph in which every vertex has degree 3. The decision problem INDUCED CYCLE asks whether a graph has an induced cycle of the specified type considered in the paper. Cubic induced-cycle NP-completeness conjecture.…
Let H be a graph. An involution-free reduction of H is the unique, up to isomorphism, involution-free graph H^* such that H⇒^* H^*, where H⇒^* H' denotes a sequence of reductions by taking the subgraph induced by the fixed points of a…
Let A be a finite domain and let Γ be a constraint language on A. Write CSP(Γ) for the ordinary constraint satisfaction problem and SCSP(Γ) for the problem asking whether an instance has a surjective satisfying assignment. Let a| a∈ A…
Let G_p,q denote the graph used as the target for (p,q)-colourings, and let the textsc{G_{p,q}}-Mixing problem ask whether the reconfiguration graph of (p,q)-colourings of an input graph is connected. Circular-colouring mixing complexity…
A Diophantine prefix is generically decidable when an algorithm decides the corresponding positive-integer Diophantine sentences on the restricted collection of inputs specified by the source's genericity condition. Consider the prefixes…
A tree is an orientation of a finite undirected tree. A tree has the ability to count if its constraint satisfaction problem can encode solving systems of linear equations over Z_p for some prime p, equivalently making it Mod_pL-hard in…
Let G and H be finite graphs, and let S be a countably infinite graph that is a reduct of a finitely bounded homogeneous structure. Suppose that G→ S→ H. A primitive-positive, or pp, construction interprets one relational structure in…
For a field F of characteristic zero, let Imm_(2^m)(X)=∑_σ∈ S_2mχ_(2^m)(σ)∏_i=1^2mx_i,σ(i), where χ_(2^m) is the irreducible character of S_2m indexed by the rectangular Young diagram (2^m). Is the family Imm_(2^m):m≥ 1 VNP-complete under…
Let M be a matrix and let per_αM denote its alpha-permanent. For a positive integer k, the notation #P refers to the relevant counting-complexity class, and P to deterministic polynomial time. Computational complexity conjecture.…
Let n≥ 1 be fixed, and let d^p_M and d^p_ I denote the corresponding distances on finitely presented n-parameter persistence modules, with d^p_ I considered specifically for 2-parameter modules. Computational complexity conjecture. (i) For…
Let G_d(N,1/2,κ) be the hypergraphic planted clique model on N vertices with fixed integer d≥2, and let E_rm HPC_D denote the sum of Type-I and Type-II errors of a test. HPC detection conjecture. If, for some τ>0,…