# Is there a counting complexity class for succint problems?

Encoding NP-complete problems succintly often makes them NEXP-complete. I am wondering if counting the number of solutions to such a problem with a succint encoding would be any harder than solving the original succint problem.

For instance, if we use a circuit encoding to represent a 3CNF formula, we obtain SUCCINCT 3SAT, which is NEXP-complete. What is the complexity of counting the number of satisfying assignments to a 3CNF formula represented as a circuit?

#NEXP would be a natural name for the resulting class, but I cannot find any reference to such a class. Can it be easily shown to be equivalent to NEXP?

The following question is related, but maybe focussing on NEXP which exhibits non-determinism would make it easier to find an appropriate answer. What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

• I guess the "natural" counting complexity class related to $\mathsf{NEXP}$ is $\#\mathsf{EXP}$ rather than $\#\mathsf{NEXP}$ and you shall find some papers on this. Also, this question (and the comments therein) is directly related to your question: $\#\mathsf{EXP}$-Complete problems. – Bruno Mar 9 '15 at 10:45