Cryptology City

Cryptology City
Home

❯

Barriers

❯

No relativizing reduction from AM to PP

Oct 04, 2026

No relativizing reduction from AM to PP

Unconditional · against relativizing reductions · Ver92

Statement

No relativizing reduction from AM to PP exists: there is an oracle relative to which AM⊆PP — Ver92.

Notes

  • Ver92 also proves MA ⊆ PP.

Graph View

  • No relativizing reduction from AM to PP
  • Statement
  • Notes

Backlinks

  • Arthur-Merlin
  • Probabilistic polynomial-time
  • MA ⊆ PP

Created with Quartz v4.5.2 © 2026

  • GitHub
  • Bluesky