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!!