CODEWITHSUNDEEP
computer-sciencetheorynp-complete
Mr. X
Mr. X

Reputation: 51

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.

Upvotes: 5

Views: 1713

Answers (5)

Albert S
Albert S

Reputation: 2602

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.

Upvotes: 0

happs
happs

Reputation: 417

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.

Upvotes: 0

Charles
Charles

Reputation: 11479

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

Upvotes: 0

Kevin Burke
Kevin Burke

Reputation: 64844

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.

Upvotes: 1

msw
msw

Reputation: 43487

Argumentum per contrarium:

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

Upvotes: 1

Related Questions