Favorite Theorem 9

Favorite Theorem 9

• Beigel, Reingold and Spielman:
  • PP is closed under intersection.
• Makes use of connection between #P functions and low-degree polynomials.
• Proof uses rational functions that closely approximate the absolute value function to combine two #P functions that define two PP languages.

Previous slide

Next slide

Back to the first slide

View Graphic Version

Fortnow-Reingold - PP closed under tt reductions.

Beigel - Oracle relative to which PNP not in PP and thus PP not closed under Turing reductions.