Open Problem Garden

Ulam, Stanislaw M.

Kelly, Paul J.

Cook, Stephen

Levin, Leonid A.

P

NP

P vs. NP ★★★★

Author(s): Cook; Levin

Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm

F_d versus F_{d+1} ★★★

Author(s): Krajicek

Problem   Find a constant such that for any there is a sequence of tautologies of depth that have polynomial (or quasi-polynomial) size proofs in depth Frege system but requires exponential size proofs.

Keywords: Frege system; short proof

Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

The deck of a graph is the multiset consisting of all unlabelled subgraphs obtained from by deleting a vertex in all possible ways (counted according to multiplicity).

Conjecture   If two graphs on vertices have the same deck, then they are isomorphic.

Keywords: reconstruction

Snevily, Hunter S.