Название более или менее говорит само за себя, но я думаю, я мог бы добавить немного фона и некоторые конкретные примеры, которые меня интересуют.
Теоретики описательной сложности, такие как Иммерман и Фагин, охарактеризовали многие из наиболее известных классов сложности с использованием логики. Например, NP может характеризоваться экзистенциальными запросами второго порядка; P можно охарактеризовать запросами первого порядка с добавленным оператором наименьшей фиксированной точки.
Мой вопрос: были ли какие-либо попытки, особенно успешные, придумать такие представления для классов квантовой сложности, как BQP или NQP? Если нет, то почему нет?
Спасибо.
Обновление (модератор) : этот вопрос полностью ответил на этот пост на mathoverflow .
Ответы:
Я думаю, что ответ Робинса на мой вопрос о МО также отвечает на этот.
Описательная сложность характеристика класса сложности дает язык , чьи запросы (т.е. формулы) в точности функции вычислимый C . Синтаксис языка, как правило, очень прост, т.е., учитывая строку q, легко проверить, является ли q правильно сформированным запросом языка, по крайней мере ожидается, что он будет решаем (но обычно проверка синтаксиса может быть выполнена в класс малой сложности). Это повлечет за собой эффективное enumerablity проблем в классе С и даст синтаксическую характеристику для C . (Если сложность проверки синтаксиса низкая, это также может означать существование полной проблемы для класса.)C C q q C C
В приведенных выше замечаний, Робин связан с Корд Eickmeyer и бумаги Мартина Grohe в « рандомизации и Derandomization в описательной теории сложности » , которая дает «описательная сложность» характеристику . Сами авторы отмечают во введении, что это отличается от того, что обычно подразумевается под описательной характеристикой сложности:BPP
источник
источник