The catalog

All problems

Every statement in the catalog, readable in place. Filters apply instantly; search covers names, IDs, and the LaTeX statements themselves.

Showing 37 of 280 problems in Theoretical computer science

NT-PRIME-016

Graph Reconstruction Conjecture

LandmarkConjecture1942

G

and

H

are finite simple graphs on the same number

n \geq 3

of vertices and the multisets of unlabeled graphs

{G - v : v \in V (G)} and {H - w : w \in V (H)}

are equal, then

G ≅ H

, where

G - v

denotes the induced graph obtained by deleting

v

OPT-001

Strongly polynomial linear programming

LandmarkOpen problem1983

There is an algorithm which, for every rational

A \in Q^{m \times n}

b \in Q^{m}

, and

c \in Q^{n}

, decides whether

max {c^{T} x : A x \leq b, x \in R^{n}}

is infeasible, unbounded, or has an optimum and, in the last case, returns an exact optimal solution, using at most

p (m, n)

elementary arithmetic operations and comparisons for one fixed polynomial

p

, while every intermediate rational number has encoding length polynomial in the total input encoding length.

TCS-001

$P$ versus $NP$

IconicOpen problem1971

P \neq = NP ?

Here

P

is the class of decision languages recognized by deterministic Turing machines in polynomial time, and

NP

is the class recognized by nondeterministic Turing machines in polynomial time (equivalently, languages with polynomial-size certificates verifiable in deterministic polynomial time).

TCS-002

$P=BPP$ Derandomization Conjecture

LandmarkConjecture1977–1985

P = BPP,

where

P

is deterministic polynomial time and

BPP

consists of languages decided by probabilistic polynomial-time Turing machines that give the correct answer with probability at least

2/3

on every input.

TCS-005

Valiant's $VP$ versus $VNP$ Conjecture

LandmarkConjecture1979

Over

Q

V P \neq = V NP .

The class

V P

consists of polynomial families

(f_{n})

, with

f_{n} \in Q [x_{1}, \dots, x_{p (n)}]

for some polynomial

p

, whose degrees and arithmetic-circuit sizes are bounded by polynomials in

n

. The class

V NP

consists of polynomial families

(g_{n})

for which there are a polynomial

q

and a family

(h_{n}) \in V P

such that

g_{n} (x) = y \in {0, 1}^{q (n)} \sum h_{n} (x, y) .

TCS-008

Exponential Time Hypothesis

LandmarkConjecture1999

No deterministic algorithm decides satisfiability of

3

-CNF formulas with

n

variables in time

2^{o (n)}

, where a

3

-CNF is a conjunction of clauses, each containing at most three literals.

TCS-011

Graph Isomorphism in Polynomial Time

LandmarkOpen problemc. 1971

Is there a deterministic polynomial-time algorithm that, given adjacency matrices of two finite simple

n

-vertex graphs

G, H

, decides whether there exists a permutation

π

of their

n

vertices satisfying

uv \in E (G) ⟺ π (u) π (v) \in E (H) for all u, v ?

TCS-012

Deterministic Polynomial-Time Integer Factoring

LandmarkOpen problemc. 1975

Is there a deterministic algorithm that, on binary input

N \geq 2

, outputs the prime factorization of

N

in time polynomial in

lo g N

TCS-013

Existence of One-Way Functions

LandmarkOpen problem1976

Does there exist a polynomial-time computable, length-preserving function family

f_{n} : {0, 1}^{n} \to {0, 1}^{n}

such that, for every probabilistic polynomial-time algorithm

A

that outputs an

n

-bit string (or failure), and every polynomial

p

, for all sufficiently large

n

x \leftarrow {0, 1}^{n}, A Pr [f_{n} (A (1^{n}, f_{n} (x))) = f_{n} (x)] < \frac{1}{p ( n )} ?

TCS-014

Quantum PCP Conjecture

LandmarkConjecturec. 2006

There exist constants

q \in N

and

0 \leq a < b \leq 1

such that the following promise problem is

QM A

-hard: given an

n

-qubit Hamiltonian

H = \sum_{i = 1}^{m} H_{i}

, where

m = poly (n)

, each

H_{i}

acts on at most

q

qubits and

0 ⪯ H_{i} ⪯ I

, distinguish

λ_{m i n} (H) \leq am from λ_{m i n} (H) \geq bm,

where

λ_{m i n} (H)

is the least eigenvalue of

H

. Here

QM A

is bounded-error quantum polynomial-time verification with a polynomial-size quantum witness.

TCS-018

Matrix Multiplication Exponent $\omega=2$

LandmarkConjecturec. 1969

Over the concrete field

Q

, let

ω = in f {τ : two n \times n matrices can be multiplied using O (n^{τ + ε}) field operations for every ε > 0} .

Then

ω = 2.

TCS-023

Deterministic Polynomial Identity Testing

LandmarkOpen problemc. 1980

Is there a deterministic polynomial-time algorithm which, given a division-free arithmetic circuit over

Q

with binary-encoded rational constants, decides whether the formal polynomial computed by the circuit is identically zero, in time polynomial in the circuit's binary encoding length?

TCS-026

Simple Stochastic Games in Polynomial Time

LandmarkOpen problem1992

A simple stochastic game is a finite directed graph whose vertices are partitioned into MAX, MIN, random, and two absorbing sink vertices labeled

0

and

1

. Every nonsink vertex has exactly two outgoing arcs. At a MAX or MIN vertex the corresponding player chooses the next vertex; at a random vertex each outgoing arc is chosen with probability

1/2

. Starting from a specified vertex

s

, MAX receives payoff

1

exactly when play eventually reaches sink

1

, and payoff

0

otherwise. If

val (s) = σ sup τ in f σ, τ Pr [reach sink 1],

where

σ

and

τ

range over strategies of MAX and MIN, is there a deterministic polynomial-time algorithm deciding whether

val (s) > \frac{1}{2}

TCS-028

Small-Set Expansion Hypothesis

LandmarkConjecture2010

For a finite

D

-regular graph

G = (V, E)

and a nonempty set

S \subseteq V

, define its edge expansion by

Φ_{G} (S) = \frac{∣ E ( S , V ∖ S ) ∣}{D ∣ S ∣},

where

E (S, V ∖ S)

is the set of edges with one endpoint in

S

and the other outside

S

. For every constant

η \in (0, 1/2)

, there is a rational constant

δ \in (0, 1/2)

such that the following promise problem is

NP

-hard, on input sizes for which

δ ∣ V ∣

is an integer:

YES: NO: some S \subseteq V with ∣ S ∣ = δ ∣ V ∣ has Φ_{G} (S) \leq η; every S \subseteq V with ∣ S ∣ = δ ∣ V ∣ has Φ_{G} (S) \geq 1 - η .

TCS-006

$NP\nsubseteq P/poly$

MajorConjecturec. 1980

There is a language in

NP

that is not decided by any family

(C_{n})_{n \geq 1}

of Boolean circuits of size polynomial in

n

, where

C_{n}

decides membership for all inputs of length

n

; in symbols,

NP ⊈ P / p o l y .

Here

NP

is nondeterministic polynomial time, and

P / p o l y

is the class defined by such polynomial-size, nonuniform circuit families.

TCS-010

Strong Exponential Time Hypothesis

MajorConjecture2001

For every

ε > 0

there exists an integer

k \geq 3

such that

k

-SAT—satisfiability of CNF formulas whose clauses contain at most

k

literals—on

n

variables cannot be decided by a deterministic algorithm in time

O ((2 - ε)^{n}) .

TCS-015

Aanderaa–Karp–Rosenberg Evasiveness Conjecture

MajorConjecturec. 1973

Fix

n

, and let

P

be a nontrivial property of simple labeled

n

-vertex graphs that is invariant under vertex permutations and monotone under adding edges, where nontrivial means that

P

is neither empty nor the set of all such graphs. Every deterministic algorithm that decides whether an unknown graph has

P

by adaptively querying edge presence has worst-case query complexity

(2 n) .

TCS-017

Berman–Hartmanis Isomorphism Conjecture

MajorConjecture1977

A, B \subseteq {0, 1}^{*}

are both

NP

-complete, where

NP

is nondeterministic polynomial time, and completeness is under polynomial-time many-one reductions, then there exists a bijection

f : {0, 1}^{*} \to {0, 1}^{*}

such that

f

and

f^{- 1}

are polynomial-time computable and

x \in A ⟺ f (x) \in B .

TCS-019

NP-Hardness of the Minimum Circuit Size Problem

MajorOpen problemc. 1975

The Minimum Circuit Size Problem (MCSP) takes as input the

N = 2^{n}

-bit truth table of a Boolean function

f : {0, 1}^{n} \to {0, 1}

and an integer

s \leq N

, and asks whether

f

has a Boolean circuit over the fixed complete basis

{AND, OR, NOT}

, with

AND

and

OR

of fan-in two, and with at most

s

gates. Is MCSP

NP

-hard under deterministic polynomial-time many-one reductions?

TCS-027

Feige's Random $3$ -SAT Refutation Hypothesis

MajorConjecture2002

For every sufficiently large constant

Δ > 0

, there is no randomized polynomial-time algorithm

A

having both of the following properties. First, for every satisfiable

3

-CNF formula

F

A (F)

never outputs

UNSAT

. Second, if

F_{n, Δ}

is formed on variables

x_{1}, \dots, x_{n}

by choosing

m = ⌊ Δ n ⌋

clauses independently and uniformly, each clause using three distinct variables with independent uniformly random signs, then

Pr [A (F_{n, Δ}) = UNSAT] ⟶ 1 as n \to \infty,

where the probability includes the randomness of both the formula and

A

TCS-029

Quantum Parallel Repetition Conjecture

MajorConjecture2004

For every finite two-player one-round game

G

whose entangled value satisfies

ω^{*} (G) < 1

, there is a constant

c_{G} > 0

such that the entangled value of the

n

-fold parallel repetition obeys

ω^{*} (G^{\otimes n}) \leq e^{- c_{G} n} (n \geq 1) .

TCS-030

Fixed-Polynomial-Factor Hardness of Euclidean Closest Vector

MajorConjecturec. 2003

There exists a constant

ε > 0

for which the following promise problem is

NP

-hard under deterministic polynomial-time many-one reductions: given a lattice basis

B \in Z^{m \times n}

, target

t \in Z^{m}

, and radius

r > 0

, distinguish

dist_{2} (t, L (B)) \leq r from dist_{2} (t, L (B)) > n^{ε} r .

INFO-006

Li–Li Undirected Network Coding Conjecture

MajorConjecture2004

For every finite undirected capacitated network with any finite collection of unicast source--sink pairs, the maximum common rate achievable by arbitrary network coding equals the maximum common rate achievable by fractional multicommodity routing.

GAME-003

Polynomial-Time Computation of a Bimatrix Nash Equilibrium

LandmarkOpen problem1994

Is there a deterministic polynomial-time algorithm that, given two rational payoff matrices

A, B \in Q^{m \times n}

, outputs mixed strategies

x \in Δ_{m}

and

y \in Δ_{n}

satisfying

x^{T} A y \geq x^{'}^{T} A y (x^{'} \in Δ_{m}), x^{T} B y \geq x^{T} B y^{'} (y^{'} \in Δ_{n})?

GAME-002

Complete EFX allocation for additive goods

MajorConjecture2016

For every finite agent set

N

, finite set

M

of indivisible goods, and nonnegative additive valuations

v_{i} (S) = \sum_{g \in S} v_{i} (g)

, there is a partition

(X_{i})_{i \in N}

M

such that, for all

i, j \in N

and every

g \in X_{j}

v_{i} (X_{i}) \geq v_{i} (X_{j} ∖ {g}) .