# 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

So I have the following language:

C = {<G,w>|G is a CFG in Chomsky normal form and w has more than one parse tree in G}

How to prove that this language is in P (decidable in deterministic polynomial time)?

I tried to come up with a polynomial-time algorithm and tried to show a reduction to a different language in P, but couldn't figure it out.

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 < 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.