Thursday, March 16, 2017

NP in ZPP implies PH in ZPP

If NP is in ZPP is the entire polynomial-time hierarchy in ZPP? I saw this result used in an old TCS Stackexchange post but I couldn't find a proof (comment if you know a reference). The proof that NP in BPP implies PH in BPP is harder than it looks and NP in BQP implies PH is in BQP is still open as far as I know.

I found a simple proof that NP in ZPP implies PH in ZPP and then an even simpler one.

Assume NP in ZPP. This implies NP in BPP so PH is also in BPP. So we need only show BPP in ZPP.

BPP is in ZPPNP follows directly by Lautemann's proof that BPP is in Σ2P or by the fact that BPP is in MA is in S2P is in ZPPNP. By assumption, BPP in ZPPNP implies BPP in ZPPZPP = ZPP.

And this is even simpler.

ZPP = RP∩co-RP in NP∩co-NP. Σ2P = NPNP in NPZPP (by assumption) in NPNP∩co-NP = NP in ZPP. You can get the higher levels of the hierarchy by an easy induction.


  1. 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.

  2. 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
    PH=Σ2=NP^NP which, by assumption is in ZPP^ZPP=ZPP.

    1. NP in ZPP implies NP^NP in NP^ZPP but not directly that NP^ZPP in ZPP^ZPP.