Algorithm to answer existential questions - Reduction
Solution 1:
I have had a chance to look at the paper now. Your description of the reduction and your understanding of the argument is perfectly correct. Your restatement of Lemma 1 is not quite right as explained by quid in acomment above.