Open Problem Garden

P vs. NP ★★★★

Author(s): Cook; Levin

Problem Is P = NP?

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

Posted by zitterbewegung
updated October 18th, 2007

add new comment

Logic

F_d versus F_{d+1} ★★★

Author(s): Krajicek

Problem Find a constant $k$ such that for any $d$ there is a sequence of tautologies of depth $k$ that have polynomial (or quasi-polynomial) size proofs in depth $d+1$ Frege system $F_{d+1}$ but requires exponential size $F_d$ proofs.

Keywords: Frege system; short proof

Posted by zitterbewegung
updated October 18th, 2007

add new comment

Graph Theory

Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

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

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

Keywords: reconstruction

Posted by zitterbewegung
updated May 4th, 2010

3 comments

Number Theory » Combinatorial N.T.

Snevily's conjecture ★★★

Author(s): Snevily

Conjecture Let $G$ be an abelian group of odd order and let $A,B \subseteq G$ satisfy $|A| = |B| = k$ . Then the elements of $A$ and $B$ may be ordered $A = \{a_1,\ldots,a_k\}$ and $B = \{b_1,\ldots,b_k\}$ so that the sums $a_1+b_1, a_2+b_2 \ldots, a_k + b_k$ are pairwise distinct.