Graph Theory

Shannon capacity of the seven-cycle ★★★

Author(s):

Problem   What is the Shannon capacity of $ C_7 $?

Keywords:

Posted by tchow
updated February 19th, 2009
add new comment
Analysis

Invariant subspace problem ★★★

Author(s):

Problem   Does every bounded linear operator on an infinite-dimensional separable Hilbert space have a non-trivial closed invariant subspace?

Keywords: subspace

Posted by tchow
updated April 11th, 2011
2 comments
Topology

Monovalued reloid restricted to atomic filter ★★

Author(s): Porton

Conjecture   A monovalued reloid restricted to an atomic filter is atomic or empty.

Weaker conjecture:

Conjecture   A (monovalued) function restricted to an atomic filter is atomic or empty.

Keywords: monovalued reloid

Posted by porton
updated February 5th, 2009
add new comment
Topology

Atomic reloids are monovalued ★★

Author(s): Porton

Conjecture   Atomic reloids are monovalued.

Keywords: atomic reloid; monovalued reloid; reloid

Posted by porton
updated February 4th, 2009
add new comment
Topology

Composition of atomic reloids ★★

Author(s): Porton

Conjecture   Composition of two atomic reloids is atomic or empty.

Keywords: atomic reloid; reloid

Posted by porton
updated February 4th, 2009
add new comment
Theoretical Comp. Sci. » Algorithms

Exponential Algorithms for Knapsack ★★

Author(s): Lipton

Conjecture  

The famous 0-1 Knapsack problem is: Given $ a_{1},a_{2},\dots,a_{n} $ and $ b $ integers, determine whether or not there are $ 0-1 $ values $ x_{1},x_{2},\dots,x_{n} $ so that $$ \sum_{i=1}^{n} a_{i}x_{i} = b.$$ The best known worst-case algorithm runs in time $ 2^{n/2} $ times a polynomial in $ n $. Is there an algorithm that runs in time $ 2^{n/3} $?

Keywords: Algorithm construction; Exponential-time algorithm; Knapsack

Posted by dick lipton
updated August 6th, 2010
7 comments