Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 considered to be NP-Complete. Now I'm just confused...any help would be appreciated.

like image 341
Mr. X Avatar asked Nov 06 '22 07:11

Mr. X


2 Answers

Argumentum per contrarium:

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

like image 75
msw Avatar answered Dec 01 '22 08:12

msw


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.

like image 22
Kevin Burke Avatar answered Dec 01 '22 07:12

Kevin Burke