Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP. Are there any known #EXP-complete problems? In particular, has #Succinct Sat (the natural candidate) been shown to be #EXP-complete?

Papadimitriou and Yannakis mention this class in a 1986 paper (1) but I have not been able to find more recent results.

As an aside, they mention an interesting natural candidate for a #EXP problem: given a number $n$ in binary, return the number of planar graphs with $n$ nodes. Is anything further known about the complexity of this problem?

  1. Papadimitriou, Christos H., and Mihalis Yannakakis. "A note on succinct representations of graphs." Information and Control 71.3 (1986): 181-185.
  • $\begingroup$ Complete under polynomial-time reductions? $\endgroup$ – usul Apr 14 '14 at 18:53
  • $\begingroup$ Yes I believe that's the natural extension $\endgroup$ – SamM Apr 14 '14 at 19:07
  • 6
    $\begingroup$ Doesn't the #EXP-completeness of #SUCCINCT CIRCUIT SAT (and hence of #SUCCINCT SAT and #SUCCINCT 3SAT), follow immediately from the reduction (simulation of a nondeterministic TM that runs in 2^n) used to prove that the decision counterpart (SUCCINCT CIURCUIT SAT) is NEXP-complete? $\endgroup$ – Marzio De Biasi Apr 14 '14 at 20:39
  • 5
    $\begingroup$ BTW, googling around I found that the problem of counting the number of simple paths in hypercubes is #EXP-complete under $\leq_{r-shift}^p$ reductions if the graphs are specified by circuits (see Maciej Liśkiewicz, Mitsunori Ogihara, Seinosuke Toda, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes ) $\endgroup$ – Marzio De Biasi Apr 14 '14 at 20:50

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.