Can we DISPROVE that a problem is NP-complete

Question

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$?

Answer 1

The provided answer is not valid to the question, as far as I know. Your rebuttal that there could be some other clever certificate is totally reasonable.

However, is it possible that you misunderstood the question? The question may be asking why this problem is not straightforwardly in NP-complete, in which case the "obvious" certificate would indeed not work, as the provided answer states.

To show that a problem is not NP-complete, there are two possibilities: it is either too easy* or too hard. For the too easy case, you can show that it can be solved in polynomial time by giving an algorithm. This shows that it is in $P$, but see the caveat below. For the too hard case, you need to show that it is at least EXPSPACE-complete, by e.g. a reduction from another EXPSPACE-complete problem such as $EQ_{REX\uparrow}$ (equivalence of regular expression with exponentiation). By space hierarchy theorem, an EXPSPACE-complete problem cannot be solved in PSPACE, which is equal to NPSPACE (by Savitch's theorem), which contains NP. You can also show that it is an NEXPTIME-complete, which properly contains NP by the time-hierarchy theorem. Note that PSPACE-complete or even EXPTIME-complete would not do, since it is unknown whether NP is strictly contained in PSPACE or EXPTIME.

* In fact, the "too easy" case is dependent on $P \neq NP$, which is open. So the most correct thing we can say is that it is unknown whether the problem is NP-complete or not.

Answer 2

What is $K$?

If $K$ is constant then this problem is in $P$. The number of paths with source s is less than $\binom{n-1}{K} \in O(n^K)$. So one can enumerate these paths in polynomial time.

At first, we will construct an algorithm, that finds one path from s to t with length $\ge K$

function has_paths(G,s,t,K):
 { for all paths (s=v_1,v_2,...v_{K_1}) in G\{t} do
     { find path from V_{k-1} to t in G\{v_1,v-2,...v_{k-2}}
  }

This algorithm can be modified, that it would search n/4 path and stop after finding it. This Version will be still in P. (Hint: use shortest path algorithm and weighted graphs)

If $K=n-1$ then to find one path is a Hamilton-path problem and NP-complete and to find $n/4$ path is NP-hard.

If $K$ is a function with $\lim_{n\to\infty} K(n) =\infty$ and $K(n)=o(n)$ then findding one path is a good candidate for the class NPI