戸田の定理の簡潔な証明

研究

Lance Fortnow の論文リストを見ていたらこんな論文が．

  • Lance Fortnow
    • "A simple proof of Toda's theorem," Theory of Computing, 5(7):135-140, 2009.

所謂 "Toda's Theorem" というのは " PH \subseteq P^{\sharp P}" という結果ですが，この論文ではその前半部分である " PH \subseteq BPP^{\oplus P}" を半ページ（但し既存の結果を引用した上でですが）で済ませています．ちなみに後半部分についても解説が書かれているので興味がある方は是非読まれることをお勧めします．