If a problem X (decision problem) is known to be NP-Complete, and proven to be reduced to problem Y, can you then say problem Y is NP-Complete?

If a problem X (decision problem) is known to be NP-Complete, and proven to be reduced to problem Y in polynomialtime, can you then say problem Y is NP-Complete?

My first thought was, no, problem Y needs to be shown that it is in NP. But after further thought, if X is reduced to Y, Y is already c开发者_Go百科onsidered to be NP-Complete. Now I'm just confused...any help would be appreciated.

---

Argumentum per contrarium:

If X ∈ NP and X ⇔ Y and Y ∉ NP then X ∉ NP.

---

Problem X - Unsure
Problem Y - In NP

To prove X is in NP, you show that you can follow steps to reduce every problem in X to a problem in Y. Then you know that the X problem is at least as hard as the equivalent Y problem.

So no, you need to start with Y and then reduce to X.

---

SAT can be solved in a single call to ALL, but that doesn't mean that ALL is in NP.

---

Yes that is correct. You can reduce your problem in polynomial time to any already known NP complete problem but that is considered to be a very difficult task. So instead you pick an already NP complete problem and reduce it to your problem and also show that it is in NP, then your problem will be NP complete.

---

Not yet, you will need a few more steps

In order to prove that a problem L is NP-complete, we need to do the following steps:

1. Prove your problem L belongs to NP (that is that given a solution you can verify it in polynomial time)
2. Select a known NP-complete problem L'
3. Describe an algorithm f that transforms L' into L
4. Prove that your algorithm is correct (formally: x ∈ L' if and only if f(x) ∈ L )
5. Prove that algo f runs in polynomial time

So far you have step 2,3,4
You still need to show that the reduction is polynomial (step 5)
And that the problem belongs to NP (step 1), that is a solution can be verified in polynomial time.