K-Hamiltonian Path problem and NP-completeness

Question

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?

• libik: The only thing that comes to my mind is that either you were told wrong (so the NP statement is not true). Or there is some trick regarding finding/veryfing existence of alternatives Hamiltonian Paths once you find the first one - where to confirm n/4 can be done faster than full search of new Hamiltonian Path. If you believe the statement is true, I would think about what is the maximum of Paths and how can I confirm existence of certain number of paths. Beside that you are correct - finding n/4 Hamiltonian Paths is n^2 complexity if you look one by one.
• user58697: IIUC, the solver doesn't produce those paths, but only answers Yes or No. Now the certifier has a hard time to verify the answer.
• CsGeek: @user58697 Oh so you mean that for any arbitrary certificate t, verifying would not be in polynomial time? Since the certificate could be any number of paths, and maybe even none of which fulfill the conditions? So even answering No means going through all these potentially exponential number of paths?
• user58697: That is my impression.