Теорема Тоды
Полиномиальная иерархия содержится в вероятностной машине Тьюринга за полиномиальное время.

Теорема Тоды — это результат теории сложности вычислений , доказанный Сейносукэ Тодой в его статье «PP is as Hard as the Polynomial-Time Hierarchy» [1] и удостоенный премии Гёделя 1998 года .

Заявление

Теорема утверждает, что вся полиномиальная иерархия PH содержится в P PP ; это подразумевает тесно связанное утверждение, что PH содержится в P #P .

Определения

#P — это проблема точного подсчета количества решений полиномиально проверяемого вопроса (то есть вопроса из NP ), в то время как, грубо говоря, PP — это проблема предоставления ответа, который является правильным более чем в половине случаев. Класс P #P состоит из всех задач, которые могут быть решены за полиномиальное время, если у вас есть доступ к мгновенным ответам на любую задачу подсчета из #P (полиномиальное время относительно оракула #P ). Таким образом, теорема Тоды подразумевает, что для любой задачи из полиномиальной иерархии существует детерминированное полиномиальное сведение по Тьюрингу к задаче подсчета . [2]

Аналогичный результат в теории сложности над вещественными числами (в смысле вещественных машин Тьюринга Блюма–Шуба–Смейла ) был доказан Саугатой Басу и Тьерри Зеллом в 2009 году [3] , а комплексный аналог теоремы Тоды был доказан Саугатой Басу в 2011 году [4].

Доказательство

Доказательство разбито на две части.

  • Во-первых, установлено, что
Σ П ⋅ Б П ⋅ ⊕ П ⊆ Б П ⋅ ⊕ П {\displaystyle \Sigma ^{P}\cdot {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}}
Доказательство использует вариацию теоремы Вэлианта–Вазирани . Поскольку содержит и замкнуто относительно дополнения, по индукции следует, что . Б П ⋅ ⊕ П {\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}}^{\sharp P}}

Вместе эти две части подразумевают

П ЧАС ⊆ Б П ⋅ ⊕ П ⊆ П ⋅ ⊕ П ⊆ П ♯ П {\displaystyle {\mathsf {PH}}\subseteq {\mathsf {BP}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}\cdot \oplus {\mathsf {P}}\subseteq {\mathsf {P}}^{\sharp P}}

Ссылки

  1. ^ Тода, Сейносукэ (октябрь 1991 г.). «PP is as Hard as the Polynomial-Time Hierarchy». Журнал SIAM по вычислениям . 20 (5): 865–877. CiteSeerX  10.1.1.121.1246 . doi :10.1137/0220053. ISSN  0097-5397.
  2. ^ Премия Гёделя 1998 года. Сейносукэ Тода
  3. ^ Саугата Басу и Тьерри Зелл (2009); Иерархия полиномов, числа Бетти и действительный аналог теоремы Тоды, в книге « Основы вычислительной математики»
  4. ^ Саугата Басу (2011); Комплексный аналог теоремы Тоды, в «Основах вычислительной математики»
Взято с "https://en.wikipedia.org/w/index.php?title=Toda%27s_theorem&oldid=961507308"