Hardness and hierarchy theorems for probabilistic quasi-polynomial time
Jin‐Yi Cai, Ajay Nerurkar, D. Sivakumar · 1999
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