Computer science

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…

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

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

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…

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.

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?

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

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

For a sequence $S$ of accesses to keys in a binary search tree with $n$ keys, let $\mathrm{OPT}(S)$ be the minimum total cost of serving $S$ by any binary search tree algorithm that may rotate the tree, even one that knows $S$ in advance. Prove or disprove that splay trees serve every access…

A sorting network on $n$ wires is a fixed sequence of comparators, each of which swaps the values on two wires if they are out of order, such that every possible input comes out sorted. What is the minimum number of comparators in a sorting network for $n=13$ inputs?

Given a real $m\times n$ matrix $A$ and a vector $b\in {\mathbb{R}}^m$, decide whether there is $x\in {\mathbb{R}}^n$ with $Ax\ge b$. Is there an algorithm whose number of arithmetic operations is bounded by a polynomial in $m$ and $n$ alone, independent of the size of the numbers in $A$ and $b$?

Prove that every set of more than $2^{n-1}$ vertices of the $n$-dimensional hypercube induces a subgraph with a vertex of degree at least $\sqrt{n}$. Gotsman and Linial showed that this implies the sensitivity conjecture, that the degree and block sensitivity of a Boolean function are bounded by a…

Give a deterministic algorithm that decides whether an integer $n$ is prime in time polynomial in the number of digits of $n$, without relying on any unproved conjecture.

Is there an algorithm that, given the code of any program and an input, correctly decides whether the program eventually halts on that input? Prove your answer.

Is there an algorithm that takes any polynomial equation with integer coefficients, in any number of unknowns, and decides whether it has a solution in integers?

Can the integers $1,2,\dots ,N$ be colored red and blue so that no Pythagorean triple $a^2+b^2=c^2$ has $a$, $b$ and $c$ all the same color? Find the largest $N$ for which this is possible, or show that it is possible for every $N$.

Among all Turing machines with 5 states and 2 symbols that halt when started on a blank tape, what is the largest number of steps $S(5)$ taken before halting? Determine $S(5)$ and prove that every 5-state machine that runs longer never halts.

Let $\vee$ be a commutative and associative binary operation and $\neg$ a unary operation on a set, satisfying Robbins's equation $\neg (\neg (a\vee b)\vee \neg (a\vee \neg b))=a$ for all $a,b$. Prove that the structure is a Boolean algebra, or find a counterexample.

Keller conjectured in 1930 that in every tiling of ${\mathbb{R}}^n$ by unit cubes, some two cubes share an entire $(n-1)$-dimensional face. For which dimensions $n$ is this true?

A set of points in the plane is in general position if no three lie on a line. An empty hexagon in such a set is a convex hexagon whose vertices are points of the set and which contains no other point of the set. Find the smallest $N$ such that every $N$ points in general position contain an empty…