PP is closed under truth-table reductions

Lance Fortnow, Nick Reingold · 2002

R. Beigel et al. (1991) showed that PP is closed under intersection and a variety of special cases of truth-table closure. In the present work, the authors extend the techniques of Beigel et al. to show that PP is closed under general polynomial-time truth-time reductions.>

Read the paper · More papers on PaperTik