Consider the K-Hamiltonian Path (KHP) decision problem stated below: KHP = (G, K), where: G = (V, E) is an undirected graph of n vertices and m edges K is a positive integer Do there exist at least n/4 Hamiltonian paths of length greater than K in G?
I have been told this problem is not in NP however I cannot wrap my head around why is that so. Can someone please elaborate? For a problem to not be in NP it has to Not have a polytime certifier, but if it takes O(n) time to verify if a path is Hamiltonian or not, then should not the solution be verified in at most n^2 steps since we only have to find n/4 hamiltonian paths?