Theoretical Comp. Sci. » Complexity » Hardness of Approximation

Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

Conjecture   For every rational $ \epsilon > 0 $ and every rational $ \Delta $, there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula $ I $ on $ n $ variables, for some $ n $, and $ m = \floor{\Delta n} $ clauses drawn uniformly at random from the set of formulas on $ n $ variables. Return with probability at least 0.5 (over the instances) that $ I $ is typical without returning typical for any instance with at least $ (1 - \epsilon)m $ simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

Posted by cwenner
updated February 27th, 2009
add new comment
Graph Theory » Algebraic G.T.

Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

Problem   Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

Posted by mdevos
updated February 25th, 2009
add new comment
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