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?

  • 4
    $\begingroup$ 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. $\endgroup$
    – Bruno
    Mar 9, 2015 at 10:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.