Open-problem statements, with their sources attached.

P ≠ NP*:

The conjecture that the complexity classes P and NP are not equal.

NP ≠ coNP*:

The conjecture that the complexity classes NP and coNP are not equal.

Strong Sensitivity Conjecture, for every Boolean function f : {0,1}^n → {0,1}, bs(f) ≤ s(f)^2.

We call this the strong sensitivity conjecture because the original sensitivity conjecture only asked for a polynomial bound in terms of s(f). Huang's celebrated result (often called the sensitivity theorem) gives a quartic bound, bs(f) ≤ s(f)^4, thereby settling the original conjecture.

Černý Conjecture*: Every synchronizing DFA with $n$ states admits a synchronizing word of length at most $(n - 1)^2$.

BMO#1

Let $(a_n)_{n \ge 1}$ and $(b_n)_{n \ge 1}$ be two sequences such that $(a_1, b_1) = (1, 2)$ and

BMO#2

Antihydra is a sequence starting at 8, and iterating the function $H(n) = \left\lfloor \frac {3n}2 \right\rfloor.$ The conjecture states that the cumulative number of odd values in this sequence is never more than twice the cumulative number of even values. It is a relatively new open problem with, so it might be solvable, although seems quite hard because of its Collatz-like flavor. The underlying Collatz-like map has been studied independently in the past, see doi:10.1017/S0017089508004655 (Corollary 4).

It is equivalent to non-termination of the 1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA 6-state Turing machine (from all-0 tape). Note that the conjecture that the machine does not halt is based on a probabilistic argument.

This machine and its mathematical reformulations were found by bbchallenge.org contributors mxdys and Rachel Hunter on June 28th 2024.

BMO#2 formulation variant

Alternative statement of beaver_math_olympiad_problem_2_antihydra using set size comparison instead of a recurrent sequence b.

BMO#5

Let $(a_n)_{n \ge 1}$ and $(b_n)_{n \ge 1}$ be two sequences such that $(a_1, b_1) = (0, 5)$ and

BMO#8

Let $(a_n)_{n \ge 1}$ and $(b_n)_{n \ge 1}$ be two sequences such that $(a_1, b_1) = (10, 12)$ and

Babai–Seress Conjecture (Conjecture 1.5)**: There exists an absolute constant $C$ such that the diameter of the alternating group $A_n$ satisfies $\operatorname{diam}(A_n) \leq n^C.$ Reference: L. Babai and Á. Seress, On the diameter of permutation groups, European Journal of Combinatorics 13 (1992), Conjecture 1.5

Babai–Seress Conjecture (Conjecture 1.7)**: There exists an absolute constant $C$ such that every finite simple non-abelian group $G$ satisfies $\operatorname{diam}(G) \leq (\log |G|)^C.$ Reference: L. Babai and Á. Seress, On the diameter of permutation groups, European Journal of Combinatorics 13 (1992), Conjecture 1.7

The Scholz conjecture, also known as the Scholz-Brauer conjecture, asserts that for every positive integer $n$, the addition-chain length of $2^n - 1$ is at most $n - 1 + \ell(n)$.