Мне любопытно, есть ли какие-либо полные проблемы в классе сложности Артура-Мерлина. Неизоморфизм графов (GNI) кажется каноническим примером проблемы в AM, но, вероятно, он не полный.
Полагаю, мне также интересно, хорошо ли определена «полная» проблема для AM. Так как AM = BP.NP, похоже, что переход к «сокращению» AM зависит от рандомизированных сокращений до 3SAT, а не от сокращений Карпа, которые мы используем для классов детерминированной сложности. Таким образом, может быть, поскольку в сокращениях Карпа нет ошибки, «приведение Карпа к проблеме АМ» на самом деле не имеет никакого значения, что делает недействительным обычное представление о том, что мы используем «полную» проблему?
Ответы:
Это неправильная интуиция. Независимо от того, как вы определяете свой класс сложности , если существует какая-либо проблема такая, что для каждой проблемы вы Если у вас есть , то является полной проблемой .C A∈C B∈C B≤pA A C
Фактически, даже проблема, которая завершается рандомизированными сокращениями для неизвестна. Другими словами, кажется, что очень трудно просто определить конкретную проблему решения в чтобы мы могли получить некоторое нетривиальное сокращение от других проблем, о которых известно, что они находятся в .AM AM AM
Это одно из препятствий на пути к поиску полной проблемы для . Это также применимо к , , - , . Эти классы требуют, чтобы вероятностная машина Тьюринга с поли-временами имела ограниченную вероятность ошибки во всех случаях. Ситуация намного проще для , этот класс не предъявляет никаких требований к вероятности ошибки, какой бы результат ни имел более высокую вероятность, является ответом машины, поэтому мы можем легко поймать для него полную проблему, а именно - .AM BPP RP co RP ZPP PP MAJ SAT
источник