Parity-P содержится в PP?

Этот вопрос был задан Яном Паксом в списке рассылки « Основы математики» . Конечно, но из ответов на этот вопрос я подозреваю , что неизвестно, будет ли (в противном случае будет одним возможный ответ на этот вопрос). Если не известно, существует ли разделение оракула? $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$ $\oplus P \subseteq PP$ $PP$

cc.complexity-theory complexity-classes Тимоти Чоу
источник

Википедия говорит, что существует оракул, для которого ( Р. Бейгель, Х. Бурман и Л. Фортноу. NP не может так же просто, как находить уникальные решения )

P^{A} = \oplus P^{A} \neq N P^{A} (= P P^{A}) = E X P^{A}

$P^A = \oplus P^A \neq NP^A ( = PP^A) = EXP^A$

Marzio De Biasi

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

То, что я собираюсь сказать, относится к другим ответам, но может быть полезно, если вы хотите, чтобы все было просто. Оракул, которого вы ищете, является всего лишь применением давно известного факта, что персептрон не может вычислить PARITY (Minsky & Papert).

Алессандро Косентино

@AlessandroCosentino Является ли и ? Что если бы были верны?

P P^{\oplus P} = P P

$PP^{\oplus P}=PP$

{\oplus P}^{P P} = P P

${\oplus P}^{PP}=PP$

P P \subseteq \oplus P

$PP\subseteq\oplus P$

T ....

Ответы:

Да, есть оракул такое , что . На самом деле, существует оракул таким образом, что . Вы можете найти результат в следующей статье. $A$ $\oplus P^A \not\subseteq PP^A$ $A$ $\oplus P^A \not\subseteq PP^{PH^A}$

Фредерик Грин, Оракул, отделяющий от , Письма для обработки информации, том 37, выпуск 3, 18 февраля 1991 года, страницы 149-153 $\oplus P$ $PP^{PH}$

Робин Котари
источник

Спасибо ... это именно то, что я искал! Во вступительных комментариях к своей статье, Грин приписывает докторскую степень Якобо Торана. тезис с первым оракула

таким образом, что

. Этот результат был впоследствии опубликован в виде теоремы 5.13 в статье Торана «Классы сложности, определяемые счетными кванторами», JACM 38 (1991), 752–773.

A

$A$

\oplus P^{A} ⊈ P P^{A}

$\oplus P^A \not\subseteq PP^A$

Тимоти Чоу

Скотт Ааронсон дает оракула, где P = PEXP, что подразумевает оракула, которого вы хотите. http://eccc.hpi-web.de/report/2005/040/download/ (теорема 12 в приложении) $\oplus$

Лэнс Фортноу
источник

Благодарю. Мне нужно выбрать только один ответ, поэтому я выбираю ответ Робина Котари, потому что это более ранняя ссылка.

Тимоти Чоу