АВПП

В информатике теоретической почти широковероятностное полиномиальное время ( AWPP ) — это класс сложности, содержащийся в PP, определенный через функции GapP . Этот класс часто возникает в контексте квантовых вычислений .

AWPP содержит класс сложности BQP (квантовое полиномиальное время с ограниченной ошибкой), который содержит задачи решения , решаемые квантовым компьютером за полиномиальное время , с вероятностью ошибки не более 1/3 для всех случаев. Фактически, это наименьший класс классической сложности, который ограничивает BQP сверху. Более того, он содержится в классе APP .

Ссылки

Общий

На данный момент, Лэнс ; Роджерс, Джон Д. (1999). «Ограничения сложности квантовых вычислений». Журнал компьютерных и системных наук . 59 (2): 240–252. arXiv : cs/9811023 . дои : 10.1006/JCSS.1999.1651 . Предоставляет информацию о связи между различными классами сложности. Доказательство BPQ в AWPP.
Феннер, Стивен А. (2003). «ПП-низость и простое определение АВПП». Теория вычислительных систем . 36 (2): 199–212. дои : 10.1007/s00224-002-1089-8 . МР 1950277 . ЕССС ТР02-036 . Определение АВПП и подключение к АПП и ПП.
Феннер, Стивен А.; Фортнау, Лэнс Дж.; Курц, Стюарт А. (1994). «Классы подсчета, определяемые пробелами» . Журнал компьютерных и системных наук . 48 (1): 116–148. дои : 10.1016/S0022-0000(05)80024-8 . МР 1259653 . Содержит определения.
Феннер, Стивен; Пока, Лэнс; Курц, Стюарт А.; Ли, Лиде (2003). «Инструментарий для построения оракулов». Информация и вычисления . 182 (2): 95–136. дои : 10.1016/S0890-5401(03)00018-X . МР 1971487 . Содержит определения.

Внешние ссылки

«Зоопарк сложности». Архивировано 1 декабря 2018 г. на Wayback Machine : содержит список классов сложности, включая AWPP, и их связь с другими классами.

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .