0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Are you sure that he didnt show that for any certificate and verification algorithm? $\endgroup$
    – nir shahar
    Dec 28, 2021 at 14:22
  • $\begingroup$ @nirshahar nope. His argument basically was that given the list of all possible paths, since the list is of length n!, there is no way to check all in polynomial time. $\endgroup$
    – eipim1
    Dec 28, 2021 at 17:57
  • $\begingroup$ Oh, then his argument is obviously not disproving this being an NP-complete problem $\endgroup$
    – nir shahar
    Dec 28, 2021 at 18:39

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "it is either too easy* or too hard" > actually, it is possible to have neither of those if $\mathsf{P}\neq \mathsf{NP}$. See this post $\endgroup$
    – Nathaniel
    Dec 28, 2021 at 18:10
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.