(Перенаправлено из почти широкого вероятностного полиномиального времени )
Перейти к навигации Перейти к поиску | Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Сентябрь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В теоретической информатике , почти широкие вероятностное полиномиальное время ( AWPP ) является класс сложности , содержащийся в ППАХ определяется с помощью ОПП функций. Класс часто возникает в контексте квантовых вычислений .
AWPP содержит класс сложности BQP (квантовое полиномиальное время с ограниченной ошибкой), который содержит задачи решения, решаемые квантовым компьютером за полиномиальное время , с вероятностью ошибки не более 1/3 для всех случаев. Фактически, это наименьший класс классической сложности, который ограничивает BQP. Кроме того, он содержится в классе APP .
Ссылки [ править ]
Общие [ править ]
- Лэнс Фортноу; Джон Роджерс. «Ограничения сложности квантовых вычислений» (PDF) . Цитировать журнал требует
|journal=( помощь ) Предоставляет информацию о связи между различными классами сложности. - Стивен А. Феннер (19 июня 2002 г.). «ПП-низкость и простое определение АРМ» . Электронный коллоквиум по вычислительной сложности. Цитировать журнал требует
|journal=( помощь ) Определение АРМ и подключение к АПП и ПП. - Лэнс Фортноу; Джон Д. Роджерс (12 ноября 1998 г.). «Ограничения сложности квантовых вычислений». arXiv : cs / 9811023 . Подтверждение BPQ в AWPP.
- «Счетные классы с определением пробелов» С. Феннера, Л. Фортноу и С. Курца из журнала Computer and System Sciences . Страницы 116–148, 1994, вып. 48. Содержит определения.
- «Набор инструментов строителя оракулов» С. Феннера, Л. Фортноу, С. Курца и Л. Ли. в 8-й структуре IEEE в материалах конференции по теории сложности. Страницы 120–131, 1993. Содержит определения.
Внешние ссылки [ править ]
- "Complexity Zoo". Архивировано 1 декабря 2018 г. на Wayback Machine : содержит список классов сложности, включая AWPP, и их отношение к другим классам.
