#open-question

Start with any positive integer $n$. If $n$ is even, replace it by $n/2$, and if $n$ is odd, replace it by $3n+1$. Repeat this forever. Prove or disprove that every starting value eventually reaches 1.

P is the class of decision problems that can be solved in polynomial time, and NP is the class of decision problems whose yes answers can be checked in polynomial time given a suitable certificate. Is P equal to NP? Equivalently, does some NP-complete problem, such as Boolean satisfiability, have a…

Twin primes are pairs of primes that differ by 2, such as $11,13$ or $41,43$. Prove that there are infinitely many twin prime pairs.

Given two graphs on $n$ vertices, decide whether they are isomorphic, that is, whether some relabeling of the vertices of one turns it into the other. Is there an algorithm that does this in time polynomial in $n$?

Prove that every even integer greater than 2 is the sum of two primes. For example $28=5+23$ and $100=3+97$.

Let $\omega$ be the infimum of all real $c$ such that two $n\times n$ matrices can be multiplied using $\mathcal{O}(n^c)$ arithmetic operations. The schoolbook method shows $\omega \le 3$, and $\omega \ge 2$ because the output has $n^2$ entries. Is $\omega =2$?

Color every point of the plane so that any two points at distance exactly 1 receive different colors. What is the smallest number of colors for which this is possible? It is known that the answer is 5, 6 or 7. Determine it.

In a unique game, variables take labels from a set of size $k$, and each constraint on a pair of variables $(u,v)$ says that the label of $v$ is a fixed permutation of the label of $u$. Prove or refute that for every $\epsilon >0$ there is a $k$ such that it is NP-hard to distinguish instances…

$n$ runners start together on a circular track of length 1 and run forever, each at its own constant speed, with all speeds different. Prove that for each runner there is a moment when every other runner is at distance at least $1/n$ along the track. The speeds $0,1,\dots ,n-1$ show that $1/n$…

A one-way function is a function $f$ that can be computed in polynomial time, but such that every probabilistic polynomial-time algorithm, given $f(x)$ for a uniformly random $x$, finds some preimage of $f(x)$ only with negligible probability. Prove or disprove that one-way functions exist.

A finite family of finite sets is union-closed if the union of any two members is again a member. Prove that every finite union-closed family that contains at least one nonempty set has an element lying in at least half of the sets of the family.

BPP is the class of decision problems solvable by a polynomial-time randomized algorithm that answers correctly with probability at least 2/3 on every input. Is every problem in BPP solvable by a deterministic polynomial-time algorithm, that is, is P = BPP?

Let $C$ be any simple closed curve in the plane. Prove or disprove that $C$ always contains four points that are the vertices of a square.

Given an integer $N$ with $b$ bits, find its prime factorization. Is there a classical (non-quantum) algorithm that does this in time polynomial in $b$?

Find a rectangular box whose three edges, three face diagonals and space diagonal all have integer lengths, or prove that none exists. In other words, find positive integers $a,b,c$ such that $a^2+b^2$, $b^2+c^2$, $a^2+c^2$ and $a^2+b^2+c^2$ are all perfect squares.

Given $n$ integers, decide whether some three of them sum to zero. A simple algorithm takes $\mathcal{O}(n^2)$ time. Is there an algorithm that runs in time $\mathcal{O}(n^{2-\epsilon })$ for some fixed $\epsilon >0$?

Prove that for every integer $n\ge 2$ there are positive integers $x,y,z$ with $\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}.$