ทฤษฎีบทของโทดะเป็นผลลัพธ์ในทฤษฎีความซับซ้อนของการคำนวณซึ่งได้รับการพิสูจน์โดยเซอิโนะสุเกะ โทดะในบทความของเขาเรื่อง "PP ยากพอๆ กับลำดับชั้นเวลาพหุนาม" ^{[ 1 ]}และได้รับรางวัล Gödel Prizeประจำ ปี 1998

ทฤษฎีบทกล่าวว่าลำดับชั้นพหุนามทั้งหมด PHบรรจุอยู่ใน P ^PPซึ่งหมายความว่ามีความสัมพันธ์อย่างใกล้ชิดกับข้อความที่ว่า PH บรรจุอยู่ในP ^#P

#Pคือคลาสของปัญหาในรูปแบบของการนับจำนวนคำตอบที่แน่นอนสำหรับคำถามที่ตรวจสอบได้ในเวลาพหุนาม (นั่นคือ สำหรับคำถามในNP ) ในขณะที่พูดอย่างคร่าวๆPPคือคลาสของปัญหาที่มีอัลกอริทึมเวลาพหุนามที่ให้คำตอบที่ถูกต้องมากกว่าครึ่งหนึ่งของเวลา คลาส P ^#Pประกอบด้วยปัญหาทั้งหมดที่สามารถแก้ไขได้ในเวลาพหุนามหากคุณสามารถเข้าถึงคำตอบทันทีสำหรับปัญหาการนับใดๆ ใน #P (เวลาพหุนามสัมพันธ์กับออราเคิล #P ) ดังนั้นทฤษฎีบทของ Toda จึงบ่งชี้ว่าสำหรับปัญหาใดๆ ในลำดับชั้นพหุนามจะมีการลด Turing แบบกำหนดได้ในเวลาพหุนามสำหรับปัญหาการนับ^{[ 2 ]}

ผลลัพธ์ที่คล้ายคลึงกันในทฤษฎีความซับซ้อนเหนือจำนวนจริง (ในความหมายของเครื่องจักรทัวริงจริงของ Blum–Shub–Smale ) ได้รับการพิสูจน์โดยSaugata BasuและThierry Zellในปี 2010 ^{[ 3 ]}และอนาล็อกเชิงซ้อนของทฤษฎีบทของ Toda ได้รับการพิสูจน์โดยSaugata Basuในปี 2011 ^{[ 4 ]}

หลักฐานนี้แบ่งออกเป็นสองส่วน

• ประการแรก ได้มีการยืนยันแล้วว่า

${\displaystyle \Sigma ^{P}\cdot {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$

การพิสูจน์ใช้ทฤษฎีบท Valiant–Vazirani ในรูปแบบที่ดัดแปลง เนื่องจาก${\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$ประกอบด้วย${\displaystyle {\mathsf {P}}}$และปิดภายใต้ส่วนเติมเต็ม จึงสรุปได้โดยการอุปมานว่า${\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}$.

• ประการที่สอง เป็นที่ยืนยันแล้วว่า

${\displaystyle {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\#P}}$

เมื่อนำทั้งสองส่วนมารวมกัน จะได้ความหมายว่า

${\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\#P}}$

ดูรายละเอียดได้ในFortnow 2009 ^{[ 5 ]}หลักฐานที่ละเอียดกว่าอยู่ในตำราArora & Barak 2009 ^{[ 6 ]}