Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/#!/StackCompSci/status/236657865786531840
polishing
Source Link
A.Schulz
A.Schulz
  • 12.3k
  • 1
  • 42
  • 64

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

  1. Prove that current problem is NP., i.e., given a certificate, prove that it can be verified in polynomial time.
  2. Take any known NP Complete-complete problem (call "Easy") and reduce all of it's instances to few instances of given problem (call "Hard"). Note this is not necessarily an 1:1 mapping.
  3. Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP Complete-complete problem in polynomial time, then all NP complete-complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

  1. Prove that current problem is NP. i.e. given a certificate, prove that it can be verified in polynomial time.
  2. Take any known NP Complete problem (call "Easy") and reduce all of it's instances to few instances of given problem (call "Hard"). Note this is not 1:1 mapping.
  3. Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP Complete problem in polynomial time, then all NP complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

  1. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified in polynomial time.
  2. Take any known NP-complete problem (call "Easy") and reduce all of it's instances to few instances of given problem (call "Hard"). Note this is not necessarily an 1:1 mapping.
  3. Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP-complete problem in polynomial time, then all NP-complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?

Source Link
Ankush
Ankush
  • 309
  • 3
  • 9

How are all NP Complete problems similar?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.

  1. Prove that current problem is NP. i.e. given a certificate, prove that it can be verified in polynomial time.
  2. Take any known NP Complete problem (call "Easy") and reduce all of it's instances to few instances of given problem (call "Hard"). Note this is not 1:1 mapping.
  3. Prove that above reduction can be done in polynomial time.

All is well here. Is this knowledge right "if you can solve any NP Complete problem in polynomial time, then all NP complete problems can be solved in polynomial time" ?

If yes, then as per above proof technique, let's say "Easy" problem can be solved in polynomial time, how does that imply "hard" can be solved in polynomial time? What am I missing here? Or is this true, that "hard" problem can be reduced to the "easy" problem too?