Теорема Тода - Todas theorem - Wikipedia

Теорема Тоды это результат теория сложности вычислений это было доказано Сейноске Тода в своей статье «PP так же сложен, как и иерархия полиномиального времени»^[1] и получил 1998 Премия Гёделя.

Заявление

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

Определения

#П проблема точного подсчета количества решений полиномиально проверяемого вопроса (то есть вопроса в НП ), а, грубо говоря, PP проблема в том, чтобы дать правильный ответ более чем в половине случаев. Класс 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 так же сложен, как и иерархия полиномиального времени». SIAM Журнал по вычислениям. 20 (5): 865–877. CiteSeerX  10.1.1.121.1246. Дои:10.1137/0220053. ISSN  0097-5397.
2. Премия Гёделя 1998 года. Сейноске Тода
3. Саугата Басу и Тьерри Зелл (2009); Полиномиальная иерархия, числа Бетти и вещественный аналог теоремы Тоды, в Основы вычислительной математики
4. Саугата Басу (2011); Комплексный аналог теоремы Тоды, в Основы вычислительной математики