I've been wrestling with a certain research problem for a few years now, and I wonder if it's an instance of a more general problem with other important instances. I'll first describe a general formulation of the problem, and then I'll reveal my particular instance.

Let $S_n$ denote a set of objects of size $n$. I am interested in subsets $G_n\subseteq S_n$ with two properties:

1. There are natural probability distributions on $S_n$ for which a random member lands in $G_n$ with high probability, so $G_n$ is ubiquitous in some sense. 

2. It seems rather difficult (and it might be impossible) to efficiently construct a member of $G_n$ along with a certificate of its membership which can be verified in polynomial time.

**Question:** Do you have an example of $G_n$ which satisfies both of these?

Here's my example: Let $S_n$ denote the set of real $m\times n$ matrices with $1\leq m\leq n$, fix a constant $C>0$, and say $\Phi\in G_n$ if the following holds for each $k$ satisfying $m\geq Ck\log(n/k)$: If $x\in\mathbb{R}^n$ has $k$ nonzero entries, then

$$\frac{1}{2}\|x\|^2\leq\|\Phi x\|^2\leq\frac{3}{2}\|x\|^2.$$

(This is essentially what it means for $\Phi$ to satisfy the restricted isometry property.) In this case, $G_n$ satisfies 1 above (provided $C$ is sufficiently large) by considering matrices with iid subgaussian entries. The fact that $G_n$ is plagued with 2 above is the subject of [this blog entry by Terry Tao][1].


  [1]: http://terrytao.wordpress.com/2007/07/02/open-question-deterministic-uup-matrices/