# Complexity of an instance of a NP-complete problem

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?

• Try emulating what you saw in class. – 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).