tag:blogger.com,1999:blog-3722233.post3468358529935078919..comments2019-12-09T05:34:57.019-05:00Comments on Computational Complexity: NP in ZPP implies PH in ZPPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-53419164966341743372017-06-13T07:47:01.733-04:002017-06-13T07:47:01.733-04:00NP in ZPP implies NP^NP in NP^ZPP but not directly...NP in ZPP implies NP^NP in NP^ZPP but not directly that NP^ZPP in ZPP^ZPP.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60969821757770062912017-06-13T00:39:14.910-04:002017-06-13T00:39:14.910-04:00You can also say that NP is in ZPP implies that NP...You can also say that NP is in ZPP implies that NP is in BPP (since ZPP is in BPP), so by Karp-Lipton theorem PH=Σ2, and so<br />PH=Σ2=NP^NP which, by assumption is in ZPP^ZPP=ZPP.Antony Antonopouloshttps://www.blogger.com/profile/08257350422980121659noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5567946892550359962017-03-17T05:51:44.988-04:002017-03-17T05:51:44.988-04:00As can be seen from your second argument, you prac...As can be seen from your second argument, you practically use that ZPP is in co-NP and thus NP is in co-NP, which implies (as you have sketched) that NP=PH.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com