Show that #SAT polynomial time Turing reduces to E-majSAT. (In other words, with an oracle for E-majSAT, you can compute #SAT(phi) in time polynomial in the size of phi. You are allowed polynomially many (in the size of phi) calls to the oracle.)

#SAT: This is a function from Boolean formulas to integers; #SAT(phi) is the number of satisfying assignments of phi.

E-majSAT:Given a Boolean formula phi over x1,...,xn and kis there a setting of the first k variables so that the majority of settings (more than half) of the rest of the variables makes phi true?