tbmbob
This completely undermines the author's main point. Constraint solvers don't solve hard leetcode problems if they can't solve large instances quickly enough.
Many hard leetcode problems can be solved fairly simply with more lax runtime requirements -- coming up with an efficient solution is a large part of the challenge.
As mentioned below, this is true for ElGamal. It is also true for all other styles of FHE scheme I'm aware of (including Ring-Learning With Errors based schemes, like this one).
In fact, if a message can only encrypt to one of a small number of ciphertexts, even more direct brute force attacks are often possible. For example, many FHE systems publish a public key. In this case, one can just encrypt E(1), E(2), etc oneself.
You are combining two distinct concepts: the answer and the 'evidence'. The answer to an NP-complete problem is always Yes or No. But, we say that we can "verify" a decision problem in polynomial time if, given an answer AND evidence, we can check that the answer is true.
For concreteness: the k-clique problem (determining if there's a clique of at least size k in a graph) is hard. But, if somebody told us the answer was Yes, and gave us appropriate evidence (say, a set of k nodes in the graph which form a clique), verifying would be easy.