<p>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?</p>

<p>Papadimitriou and Yannakis mention this class in a 1986 <a href="http://ac.els-cdn.com/S0019995886800092/1-s2.0-S0019995886800092-main.pdf?_tid=9028b852-c3f7-11e3-85e3-00000aacb35f&amp;acdnat=1397495559_860f378da7efabfba882b275f2e11c9d" rel="nofollow">paper</a> (1) but I have not been able to find more recent results.   </p>

<p>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?</p>

<ol>
<li>Papadimitriou, Christos H., and Mihalis Yannakakis. "A note on succinct representations of graphs." Information and Control 71.3 (1986): 181-185.</li>
</ol>

CC BY-SA 3.0
2014-04-14T18:53:36.853Z
Complete under *polynomial-time* reductions?
usul
CC BY-SA 3.0
2014-04-14T19:07:28.973Z
Yes I believe that's the natural extension
SamM
CC BY-SA 3.0
2014-04-14T20:39:04.147Z
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
CC BY-SA 3.0
2014-04-14T20:50:39.590Z
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](http://www.sciencedirect.com/science/article/pii/S030439750300080X) )
Marzio De Biasi
<reference-request><graph-theory><counting-complexity><nexp>
#EXP-Complete problems
SamM
# #EXP-Complete problems

(Asked by: username_0 on 2014-04-14)

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](http://ac.els-cdn.com/S0019995886800092/1-s2.0-S0019995886800092-main.pdf?_tid=9028b852-c3f7-11e3-85e3-00000aacb35f&acdnat=1397495559_860f378da7efabfba882b275f2e11c9d) (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.

**Tags:** reference-request, graph-theory, counting-complexity, nexp
> **Comments:**
> **username_1**: Complete under *polynomial-time* reductions?  
> **username_0**: Yes I believe that's the natural extension  
> **username_2**: 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?  
> **username_2**: 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](http://www.sciencedirect.com/science/article/pii/S030439750300080X) )  

---

## 0 answers

