Open-problem statements, with their sources attached.

Determine whether $\mathbf{P}=\mathbf{NP}$: can every decision problem whose solutions are verifiable in polynomial time also be solved in polynomial time?

Every synchronizing deterministic finite automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$.

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$.