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 considered 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With