# #EXP-Complete problems

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.
• Complete under polynomial-time reductions? – usul Apr 14 '14 at 18:53
• Yes I believe that's the natural extension – SamM Apr 14 '14 at 19:07
• 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? – Marzio De Biasi Apr 14 '14 at 20:39
• 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 ) – Marzio De Biasi Apr 14 '14 at 20:50