Переместил мой комментарий сюда после запроса Суреша.
Пример естественной проблемы, для которой нам известны только алгоритмы, требующие ошибки с обеих сторон, заключается в следующем: с учетом трех алгебраических схем определите, являются ли ровно две из них идентичными. Это происходит из-за того, что решение о том, являются ли две алгебраические схемы идентичными, принимается совместно.
Ссылка: см. Пост Сколько сторон вашей ошибки? (2 декабря 2008 г.) о том же самом вопросе в блоге Лэнса Фортнау и комментариях ниже его поста для обсуждения естественности проблемы.
Хотя запрос факторов без абелевых нормальных подгрупп может показаться эксцентричным, класс групп без абелевых нормальных подгрупп (иногда называемых полупростыми) на самом деле довольно естественен с точки зрения структурной теории групп. См. [2] и ссылки там.
Ответы:
Переместил мой комментарий сюда после запроса Суреша.
Пример естественной проблемы, для которой нам известны только алгоритмы, требующие ошибки с обеих сторон, заключается в следующем: с учетом трех алгебраических схем определите, являются ли ровно две из них идентичными. Это происходит из-за того, что решение о том, являются ли две алгебраические схемы идентичными, принимается совместно.
Ссылка: см. Пост Сколько сторон вашей ошибки? (2 декабря 2008 г.) о том же самом вопросе в блоге Лэнса Фортнау и комментариях ниже его поста для обсуждения естественности проблемы.
источник
Хотя запрос факторов без абелевых нормальных подгрупп может показаться эксцентричным, класс групп без абелевых нормальных подгрупп (иногда называемых полупростыми) на самом деле довольно естественен с точки зрения структурной теории групп. См. [2] и ссылки там.
[1] Л. Бабай, Р. Билс, А. Сересс. Полиномиально-временная теория матричных групп . STOC 2009.
[2] Л. Бабай, П. Коденотти, Ю. Цяо. Тест изоморфизма полиномиального времени для групп без абелевых нормальных подгрупп . Появиться, ICALP 2012.
источник