• Member for 11 years
  • Last seen more than a week ago
How is proving a context free language to be ambiguous undecidable?
Accepted answer
32 votes

We reduce from Post's Correspondence Problem. Suppose we can, in fact, decide the language $\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ ambiguous}\}$. Given $\alpha_1, \ldots, \alpha_m, \...

View answer
Constructions better than a random one.
11 votes

Ramanujan graphs have second eigenvalue $\lambda_2\leq \frac{2\sqrt{D-1}}{D}$ (with $D$ the degree of the graph), while random graphs only achieve $\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$ w.h.p. ...

View answer
Algorithms from the Book.
11 votes

Lenstra-Lenstra-Lovász Lattice Basis Reduction. Maybe not quite from the book (since it's, at least to me, a bit messy), but it definitely is worth a mention here.

View answer
Hardness of finding a word of length at most $k$ accepted by a nondeterministic pushdown automaton
0 votes

A probably suboptimal method: Run Djikstra's algorithm. Then, for each final state, compare the distances with $k$. If any are $\leq k$, accept. Reject. EDIT: The above only works for NFAs! Sorry ...

View answer