- 4 A Show That If Np P Then Np Complete Np P Cnp Hard 10 Marks B For A Conventional Computer N Bits Can Rep 1 (66.05 KiB) Viewed 126 times
4. (a) Show that if NP =P, then NP-Complete = NP =P CNP-hard. (10 marks) (b) For a conventional computer, n bits can rep
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
4. (a) Show that if NP =P, then NP-Complete = NP =P CNP-hard. (10 marks) (b) For a conventional computer, n bits can rep
4. (a) Show that if NP =P, then NP-Complete = NP =P CNP-hard. (10 marks) (b) For a conventional computer, n bits can represent only 1 state at a time (e.g., 4-bit 1000 or 0101); for a quantum computer, amazingly, n qu-bits can represent 2" states at the same time. Therefore, someone proposes to show NP = P by using a quantum computer. Do you believe that such a quantum computer can make NP = P? Justify your opinion. (Hint: Is a quantum computer non-deterministic?) (10 marks)
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!