Is this language in NP?

Question

L={[G, K] | G is a simple undirected graph with no simple path longer than k}

(Further, is it Co-NP)?

I believe this is NP. I could provide a verifier that did the following:

V(G,E, k) is a verifier, where G is the graph, E is an edge list for the graph, and k is the path provided.

First, check to make sure the path is valid. Second, Begin searching for a path longer than the given path. If there is one, it can be found in polynomial time. However, if there is NOT one, because this is an undirected graph, this could check for an infinite amount of time, making this problem NP-Hard.

Where are the flaws in my thought process?

Answer 1

The complement of your problem L, call it L', is ``Given a graph G=(V,E) and an integer k, does G contain a simple path of length at least k+1'', which is the well-known LONGEST-PATH problem. The problem L' is clearly in NP: Just guess the path, assuming there is one. (Equivalently, given a path, just verify it is indeed of length at least k+1.) Note that the problem is in coNP if and only if its complement is in NP, meaning L is in coNP.

Because LONGEST-PATH is NP-complete, L is not in NP unless coNP=NP. (Because we believe coNP != NP, this implies no NP-complete problem can belong to coNP and no coNP-complete problem can belong to NP. See Arora-Barak book for details.)