Comment by danbruc

The parent comment is correct, if you can count the solutions, it is easy to find a solution. Assuming there is a solution, you set the first variable to either true or false and then count the solutions. If it is zero, you made the wrong choice and the first variable must be set to the opposite value. Repeat for the remaining variables until you have fixed all of them and found a solution. This takes n invocations of the counting algorithm and is probably what the parent comment means with O(n) even though this is not correct as it is O(n times whatever the counting algorithm runtime is) and not just O(n).

But the parent comment also missed my point. They have an algorithm for the counting problem which also provides a subexponential algorithm for the decision and search problem. But they could have refuted the exponential time hypothesis with a subexponential search or decisions algorithm which would not [easily] provide a subexponential counting algorithm.