Проблема в BPP, но неизвестно в RP или co-RP

Ответы:

21

Переместил мой комментарий сюда после запроса Суреша.

Пример естественной проблемы, для которой нам известны только алгоритмы, требующие ошибки с обеих сторон, заключается в следующем: с учетом трех алгебраических схем определите, являются ли ровно две из них идентичными. Это происходит из-за того, что решение о том, являются ли две алгебраические схемы идентичными, принимается совместно.

Ссылка: см. Пост Сколько сторон вашей ошибки? (2 декабря 2008 г.) о том же самом вопросе в блоге Лэнса Фортнау и комментариях ниже его поста для обсуждения естественности проблемы.

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

BPPRPcoRPcoRPpNdAd×dFpANBPP

Хотя запрос факторов без абелевых нормальных подгрупп может показаться эксцентричным, класс групп без абелевых нормальных подгрупп (иногда называемых полупростыми) на самом деле довольно естественен с точки зрения структурной теории групп. См. [2] и ссылки там.

[1] Л. Бабай, Р. Билс, А. Сересс. Полиномиально-временная теория матричных групп . STOC 2009.

[2] Л. Бабай, П. Коденотти, Ю. Цяо. Тест изоморфизма полиномиального времени для групп без абелевых нормальных подгрупп . Появиться, ICALP 2012.

Джошуа Грохов
источник