Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time
You can modify the CYK parsing algorithm so that it counts the number of parse trees for each word.
Given a word $w = w_1 \ldots w_n$, for each $1 \leq i \leq j \leq n$ and non-terminal $A$, we will count the number of parse trees rooted at $A$ and generating $w_i \ldots w_j$. If $i = j$ then this number is either zero or one, depending on whether $A \to w_i$ is a rule. Otherwise, all parse trees are of the form $$A \to BC \to^* (w_i \ldots w_k) (w_{k+1} \ldots w_j)$$
and so if we know, for each $i \leq k &lt; j$ and for each $B,C$ such that a rule $A \to BC$ exists, how many parse trees there are for $w_i \ldots w_k$ rooted at $B$ and for $w_{k+1} \ldots w_j$ rooted at $C$, then we can count the number of parse trees of $w_i \ldots w_j$ rooted at $A$.
You are interested in whether the number of parse trees of $w_1 \ldots w_n$ rooted at $S$ is larger than one or not. Therefore you can cap the numbers at two, thus avoiding large numbers and so reducing the running time.