1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you that was really helpful. I am looking for a decision problem that is not in NP and thought I'd try to define my own. Since counting simple paths is #P-complete, would the decision problem "does the graph G of size n contain at least 2^n simple paths of length n" not be in NP? That is assuming #P != NP $\endgroup$ – Sapas Sep 10 '18 at 5:11
  • $\begingroup$ You can't really compare #P and NP because one is a class of decision problems, and the other a class of counting problems. This was a mistake in my answer. I corrected it, and showed why (conditionally) such a problem should not be in NP. $\endgroup$ – Tom van der Zanden Sep 10 '18 at 21:51
  • $\begingroup$ Ok cool that is the idea I was looking for. This has been really helpful, I can't thank you enough!! $\endgroup$ – Sapas Sep 11 '18 at 7:23
1
$\begingroup$

It depends on the particular problem. The specific problem you mentioned can be solved in polynomial time: if $M$ is the adjacency matrix of the graph, then $\sum_{i,j} (M^n)_{i,j}$ counts the number of distinct paths of length $n$, where $M^n$ is the $n$th power of the matrix. (Here I am assuming the paths need not be simple.) This illustrates the difficulty of proving lower bounds. Just because one algorithm takes exponential time doesn't necessarily mean that all possible algorithms will take exponential time.

$\endgroup$
  • $\begingroup$ Thanks, I was trying to come up with a polynomial time algorithm but couldn't think of one. If the problem is restricted to finding simple paths of length n do you think it would still be in P? Thank you for your help and time :) $\endgroup$ – Sapas Sep 9 '18 at 5:47
0
$\begingroup$

Succinct graphs typically work by describing the graph in some "programmatic" way, e.g., by giving an automaton or logical formula which accepts the string "$x,y$" iff there's an edge $xy$ in the graph.

If you don't mind unnatural problems, you can stick with adjacency matrices or lists and get hard problems by encoding strings as graphs. For example, you could code the string $001011$ as

o          o     o  o    o
|\         |     |  |   / \
| o--o--o--o--o--o--o--o   o
|/                      \ /
o                        o

where the triangle and square distinguish the two ends of the string so you know which direction to read it. Now, any language over $\{0,1\}^*$ is a graph problem, so you can just pick any problem known not to be in NP (e.g., something NEXP-complete) and code it a graphs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.