Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time
We prove tight hierarchy theorems for bounded error probabilistic quasi-polynomial time classes, under se”era1 hardness assumptions. We show that if either (1) the Permanent does not have a subexponential time BP algorithm, or (2) some function in EXPTIME does not have subexponential size circuits, then for every lSa<D,