PP Is Closed under Truth-Table Reductions

Beigel, Reingold, and Spielman (J. Comput. System Sci. 50, 191–202 (1995)) showed that PP is closed under intersection and a variety of special cases of polynomial-time truth-table closure. We extend their techniques to show that PP is closed under general polynomial-time truth-table reductions. We also show that PP is closed under constant-round truth-table reductions.

Authors

• Lance Fortnow
• Nick Reingold

Keywords

No keywords are indexed for this paper.