Computer Science Asked by mwit30 room8 on December 4, 2021
I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?
- If problem B is in P and A reduces to B, then problem A is in P.
- Problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
- Problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.
My questions are (if I then II then(?) III/I. If III/I and III/II then IV.)
When it comes to polynomial time reductions from $A$ to $B$, I find it useful to think of it as "Solving problem $A$ by converting it to problem $B$, then using a 'Problem $B$ Solver'."
With this in mind:
Answered by Richie Yeung on December 4, 2021
I. I was not able to parse the question, sorry.
II. There is an infinite number of NP-complete problems.
III/I. Each NP-complete problem can be reduced to any other NP-complete problem.
III/II. If you show that there exists a (Karp) reduction from a NP-complete $B$ problem to a problem in P, then you have proved that all problems that reduce to $B$ are also in P. In particular this implies NP $subseteq$ P, and hence P=NP.
IV. If a NP-complete problem is in P, then P=NP.
Answered by Steven on December 4, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP