tag:blogger.com,1999:blog-3722233.post3468358529935078919..comments2024-06-13T23:23:44.643-05:00Comments on Computational Complexity: NP in ZPP implies PH in ZPPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-44265323471663106652023-11-21T15:46:30.833-06:002023-11-21T15:46:30.833-06:00Probably not because that would imply Simga_2 in P...Probably not because that would imply Simga_2 in Pi_2 and the polynomial-time hierarchy collapses. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22754843117326829382023-11-21T13:18:23.525-06:002023-11-21T13:18:23.525-06:00Can you elaborate why \Sigma_2^{P} \subseteq ZPP^{...Can you elaborate why \Sigma_2^{P} \subseteq ZPP^{NP}?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18976201556538491082021-11-26T15:18:15.242-06:002021-11-26T15:18:15.242-06:00ZPP means always correct in expected poly time. So...ZPP means always correct in expected poly time. So a ZPP^ZPP machine just simulates the oracle with its queries. Since the expectation of a sum is the sum of the expectations, the poly # of queries can be simulated in an expected polynomial number of steps. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72402385158608267062021-11-26T03:18:48.480-06:002021-11-26T03:18:48.480-06:00Can someone explain why ZPP^ZPP = ZPP?Can someone explain why ZPP^ZPP = ZPP?Anonymoushttps://www.blogger.com/profile/04441397601709203375noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69957641747060891402021-04-13T22:19:15.127-05:002021-04-13T22:19:15.127-05:00Full question.
Explicitly I want to identify rela...Full question.<br /><br />Explicitly I want to identify relation between UP and ZPP since we do not even know ZPP is in SPP although we believe it to be true.<br />In proposition 1.3 in https://dl.acm.org/doi/abs/10.1145/203610.203611 it is stated #.NP=#.P^NP iff NP=UP^NP iff NP=coNP.<br />Theorem 7.2 in On counting and approximation (springer.com) states span-P is approximable in BPP^NP.<br />NP in ZPP implies span-P is approximable in ZPP.<br /><br />1. span-P is in #(P^NP) and soI wonder if NP=ZPP would we get span-P in #P and so by theorem 4.9 UP=NP=ZPP?<br /><br />Ordinarily is ZPP low for NP? So we get:<br /><br />2. NP in ZPP implies NP=coNP and so ZPP=NP=UP^NP=UP^ZPP holds and so is ZPP low for UP providing NP=ZPP=UP?<br />So could NP=ZPP have any implications to UP and ZPP.<br /><br />Assume further UP=coUP and so UPH collapses to UP. We already assumed NP=ZPP holds. So UP is in ZPP and in NP.<br /><br />3. At least would it say something about the lowness UP making ZPP^UP in UP?<br /><br />4. coUP=UP in EP in NP=ZPP=coNP holds under assumptions. EP is known to be in SPP. Is EP known to be in UPH under the assumptions?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90928259219361443972021-04-13T21:01:29.598-05:002021-04-13T21:01:29.598-05:00In proposition 1.3 in https://dl.acm.org/doi/abs/1...In proposition 1.3 in https://dl.acm.org/doi/abs/10.1145/203610.203611 it is stated #.NP=#.P^NP iff NP=UP^NP iff NP=coNP.<br /><br />NP in ZPP implies NP=coNP and so ZPP=NP=UP^NP=UP^ZPP holds and so is ZPP low for UP providing ZPP=UP?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78998176774877468152021-04-13T20:59:28.971-05:002021-04-13T20:59:28.971-05:00In proposition 1.3 in https://www.semanticscholar....In proposition 1.3 in https://www.semanticscholar.org/paper/The-Satanic-Notations%3A-Counting-Classes-beyond-%23p-1-Hemaspaandra/c01bebe8da499eb6a585c36cde9a71a406db41e6 it is shown <br /><br />#.NP=#.P^NP iff NP=UP^NP iff NP=coNP.<br /><br />NP in ZPP implies NP=coNP and so ZPP=NP=UP^NP=UP^ZPP holds and so is ZPP low for UP providing ZPP=UP?<br /><br />Thank you.Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53419164966341743372017-06-13T06:47:01.733-05:002017-06-13T06:47:01.733-05: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-12T23:39:14.910-05:002017-06-12T23:39:14.910-05: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-17T04:51:44.988-05:002017-03-17T04:51:44.988-05: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