#complexity-theory

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

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