I am trying to prove the NP-Completeness of problem [A].

I know there is a well-known NP-Complete problem called problem [B].

I can model [A] into an instance of [B] ([B] is a very general problem and when I assign some edges a weight value then it becomes [A]).

Is this sufficient to say [A] is NP-Complete?

  • $\begingroup$ Try emulating what you saw in class. $\endgroup$ – Yuval Filmus Dec 25 '18 at 6:05

To show $A$ is NP-complete, you need to prove the following:

  1. $A \in \mathbf{NP}$
  2. $A$ is NP-hard: any problem $B \in \mathbf{NP}$ is poly-time (many-one) reducible to $A$


    equivalently (because reduction relations are transitive): there is an NP-hard problem $B$ which is poly-time (many-one) reducible to $B$.

You have shown neither, so you cannot say $A$ is NP-complete.

What you did do is a many-one reduction from $A$ to $B$, but you want the other way around. In addition, you also need to show the reduction is efficient, that is, takes polynomial time; you did not explicitly state whether this is the case. And, of course, you must not forget to show $A \in \mathbf{NP}$ (which is usually the easier part).


Your Answer

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

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