Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let T be a tournament, and let overrightarrowω(T) denote the minimum, over all orderings of V(T), of the clique number of the corresponding backedge graph. The 2-DIOMEGA-ORDERING conjecture. The problem of deciding whether…
Let Y=⟨ P,≤⟩ be Young's lattice, where P is the set of partitions ordered by inclusion of their Young diagrams. The Sigma-1 theory conjecture. The Σ_1-theory of Young's lattice Y=⟨ P,≤⟩ is NP-complete. The preceding discussion establishes…
Let $Z^{\mathrm{demi}\mathcal Q}[\mathbb{B}]$ be a demi-quantum game whose initial quantum board $\mathbb{B}$ is a superposition of positions, and call it classically reachable when $\mathbb{B}$ is reachable from a classical position. A…
An MVB instance consists of variables (l_i,r_i)_1≤ i≤ n, with recurrence t(G)= 1 if G≤ 0, 1+min_1≤ i≤ n(t(G-l_i)+t(G-r_i)) if G>0. Its variable ratios are denoted by φ_i. The MVB conjecture. For each instance of MVB, there exists a gap H…
Let $Z=(B,\Sigma,\rho_L,\rho_R,b_0)$ be a combinatorial game instance, and let $\mathbb{B}=[b_1|\cdots|b_s]$ be a quantum board consisting of a superposition of distinct positions. The associated demi-quantum game $Z^{\mathrm{demi}\mathcal…
Let EqualityStanley_k denote the relevant equality-verification problem for the kth Stanley inequality. EqualityStanley completeness conjecture. The problem EqualityStanley_k is C_=P-complete for sufficiently large k. The source presents…
Let P_N and Q_N be distributions on R^N, and let χ^2(P_N|Q_N):=E_x~Q_N[dP_N(x)/dQ_N(x)]^2-1. Write χ^2_≤ D(P_N|Q_N) for its projection onto the space of degree-D polynomials. Strong detection means success probability 1-o(1), while weak…
Let f be a polynomial-time algorithm, viewed as a function symbol of PV, and let φ_P = NP(f):= ∀ x ∀ y [ψ_SAT(x,y) → ψ_SAT(x,f(x))] where ψ_SAT(x,y) expresses that y satisfies the Boolean formula encoded by x. Unprovability conjecture. For…
A decision problem is in co-NP if its negation is in NP. A problem is NP-complete if it lies in NP and is NP-hard. NP versus co-NP conjecture. NP not= co-NP. Hence, an NP-complete problem does not lie in co-NP. This is another widely…
Let the secret key be s~_unifF_2^k and let the noise rate be η=0.05. A noisy observation is y=⟨ s,x⟩⊕Bern(η), where x~_unifF_2^k. Learning parity with noise conjecture. Any polynomial-time algorithm with Ω(1)-time query access to these…
The Fooling-Set-Submatrix problem takes integers n,m and an m× m 0/1-matrix A as input, and asks whether A contains a fooling-set submatrix of size n. NP-hardness conjecture. The Fooling-Set-Submatrix problem is NP-hard. The computational…
For a digraph D, let inv(D) be its inversion number, and let k be a fixed positive integer. Bang-Jensen et al.'s complexity conjecture. Deciding whether a given digraph D has inversion number at most k is NP-complete for any fixed positive…
The complexity classes VP_ws and VNP are considered through representation-theoretic multiplicities associated with them. Mulmuley–Sohoni multiplicity conjecture. There exist representation-theoretic multiplicities that are zero for VP_ws…
For a tournament T, let vecχ_rm a(T) denote its acyclic dichromatic number. A fixed integer k≥3 is treated as a constant rather than part of the input. Tournament acyclic dicolouring algorithm conjecture. For every fixed k≥3, it is…
Let F=Φ_M_M=2^∞ be a family of ensembles Φ_M=φ_M;n_n=1^2M⊆C^M which yield almost injective intensity measurements and have complex rational entries that can be computed in polynomial time. The consistency conjecture. Then…
Let (cal P) be a properly posed problem, and let cal S^+_c denote the positive canonical dual feasible set; write intcal S^+_c for its interior. Criterion of NP-hardness. The problem (cal P) is NP-hard if and only if intcal S^+_c=∅. This…
Let P and Q be probability measures for a high-dimensional hypothesis-testing problem based on Y∈ R^N, with N=N_n and parameters scaling with n. Let P_D be the polynomials on R^N_n of degree at most D, and define the low-degree advantage…
Let bA be an algebra with a Taylor term in its clone, and let R be a finite set of relations compatible with bA. Write CSP(R) for the constraint satisfaction problem over R. An algebra is idempotent if every basic operation satisfies…
Let d≥ 3 be the maximum degree, let ℓ be the activity, and let ℓ_c(d)=(d-1)^d-1/(d-2)^d be the critical activity for decay of correlations on the infinite d-regular tree. Consider the weighted sum of independent sets, with each independent…
Let φ be a [?]