6 problems

Karp–Cook separation conjecture. The set of problems that are ${\mathsf{NP}}$-complete using Karp reductions is a strict subset of the set of problems that are ${\mathsf{NP}}$-comp…

Let $U,V\subseteq\mathbb{N}$ be disjoint $\mathbf{NP}$-sets. A separator for $U$ and $V$ is a polynomial-time computable set $S\subseteq\mathbb{N}$ such that $U\subseteq S$ and…

NP versus co-NP conjecture.

P versus NP conjecture.

When languages are encoded as subsets of a finite-alphabet string space, two languages are p-isomorphic if a polynomial-time computable bijection of the string space, with polynomi…

The problem ${\sc 3\text{-}sat}$ is a decision problem, and an algorithm solves it in polynomial time if its running time is bounded by a polynomial in the input size. The 3-SAT ha…