Twierdzenie Tody

Twierdzenie Tody jest wynikiem teorii złożoności obliczeniowej , które zostało udowodnione przez Seinosuke Toda w jego artykule „PP jest tak trudne jak hierarchia czasu wielomianowego” i otrzymało nagrodę Gödla w 1998 roku .

Oświadczenie

Twierdzenie stwierdza, że ​​cała hierarchia wielomianów PH jest zawarta w P ^PP ; implikuje to ściśle powiązane stwierdzenie, że PH jest zawarte w P ^#P .

Definicje

#P to problem dokładnego policzenia liczby rozwiązań pytania weryfikowalnego wielomianowo (czyli pytania w NP ), podczas gdy luźno mówiąc, PP to problem udzielenia poprawnej odpowiedzi w ponad połowie przypadków. Klasa P ^#P składa się ze wszystkich problemów, które można rozwiązać w czasie wielomianowym, jeśli masz dostęp do natychmiastowych odpowiedzi na dowolny problem zliczania w #P (czas wielomianowy względem wyroczni #P ) . Zatem twierdzenie Tody implikuje, że dla każdego problemu w hierarchii wielomianów istnieje determinizm do problemu zliczania w czasie wielomianowym .

Analogiczny wynik w teorii złożoności na liczbach rzeczywistych (w sensie rzeczywistych maszyn Turinga Bluma – Shuba – Smale'a ) udowodnili Saugata Basu i Thierry Zell w 2009 r., A złożoną analogię twierdzenia Tody udowodnił Saugata Basu w 2011 r.

Dowód

Dowód jest podzielony na dwie części.

• Po pierwsze, ustalono, że

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

Dowód wykorzystuje odmianę twierdzenia Valianta – Vaziraniego . Ponieważ ${\ Displaystyle {\ mathsf {BP}} \ cdot \ oplus {\ mathsf {P}}}$ zawiera ${\ Displaystyle {\ mathsf {P}}}$ i jest zamknięty pod dopełnieniem, przez indukcję wynika, że ${\ Displaystyle {\ mathsf {PH}} \ subseteq {\ mathsf {BP}} \ cdot \ oplus {\ mathsf {P}}}$ .

• Po drugie, ustalono, że

${\ Displaystyle {\ mathsf {BP}} \ cdot \ oplus {\ mathsf {P}} \ subseteq {\ mathsf {P}} ^ {\ ostry P. }}$

Obie części oznaczają razem

${\ Displaystyle {\ mathsf {PH}} \ subseteq {\ mathsf {BP}} \ cdot \ oplus {\ mathsf {P}} \ subseteq { \mathsf {P}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\sharp P}}$