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]

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 96 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 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)