Defining a graph decision problem not in NP I have been doing some research online looking for graph problems that are decidable but not in NP. I have found the concept of succinct graphs, which if I understand properly, consist of making the input small (i.e. supplying the graph structure using a small amount of memory) so that when properties of the graph are checked, the time taken is larger than polynomial on the size of the input (and so taking problems that are in P into NP, and problems that are in NP into NEXP).

What I was wondering is whether you could do something similar but by suppliying the graph in a "standard" way (i.e. adjacency matrix), but then asking a question with a "large" answer. For instance would the following problem not be in NP?

Given a graph G = (V,E), of size n, does it contain 2^n distinct paths of size n?

To me it feels like a a certificate could not be checked in polynomial time, and so this problem cannot be in NP. I was wondering if anyone has thought of something similar, or whether there is something you could check in polynomial time that would answer this question without explicitly listing out 2^n paths. 

Any input is greatly appreciated. Thanks!!
Problems of the type "Count the number of [object]", where "[object]" is something that can be verified in polynomial time, are essentially what defines the class $\#P$ ($\textrm{Sharp-}P$). $\#P$ is the counting variant of $NP$.

As pointed out by @D.W., the problem you picked just so happens to be in $P$, but if you had picked some other problem (such as counting simple paths) it would have been $\#P$-complete.

If you take a $\#P$-complete counting problem, then the decision-counting variant ("are there at least $x$ many objects [...]") can not be in $NP$, unless the polynomial hierarchy collapses. This follows by Toda's theorem, which states that $PH\subseteq P^{\#P}$. If such a decision-counting problem would be in $NP$, we could use a polynomial number of calls to an $NP$ oracle to compute the exact number (by binary search). Thus $P^{\#P}$ would be equal to $P^{NP}$ and the polynomial hierarchy collapses.