Is the following line true?

Consider three problems A, B and C. If $A$ $<p$ $B$ and $B$ $<p$ $C$ and $B$ is NP-complete problem, then $C$ is also NP-complete.

If B is NP-complete, then C would have also been NP-complete if it was in NP but it is not given here. Can we consider it false? Or is there any other reason?

  • 2
    $\begingroup$ You are correct, all we know about $C$ is that it is $\mathsf{NP}$-hard. By the way, the fact that $A \leq^m_p B$ is irrelevant. $\endgroup$ Jun 13, 2021 at 9:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.