So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be proved.
In the solution that the instructor sent us, they proved that we cannot prove that this problem is in NP; therefore, we cannot prove that it is in NP-complete. What he did was basically create a certificate which could not be checked in polynomial time. Is this a valid way to prove that a problem cannot be proved to be NP-complete (aside from the fact that it is not even disproving the claim.)? Because there might exist another certificate which could have been checked in polynomial time.
The problem was: Do there exist at least $n/4$ paths of $length ≥ K$ in a graph $G$ from source $s$ to destination $t$?