AWPP

W informatyce teoretycznej prawie szeroki probabilistyczny czas wielomianowy ( AWPP ) to klasa złożoności zawarta w PP zdefiniowana za pomocą funkcji GapP . Klasa często pojawia się w kontekście obliczeń kwantowych .

AWPP zawiera klasę złożoności BQP (kwantowy czas wielomianowy z ograniczonym błędem), która zawiera problemy decyzyjne rozwiązywane przez komputer kwantowy w czasie wielomianowym , z prawdopodobieństwem błędu co najwyżej 1/3 dla wszystkich instancji. W rzeczywistości jest to najmniejsza klasyczna klasa złożoności, która przekracza górne granice BQP. Ponadto jest zawarty w klasie APP.

Ogólny

• Lance Fortnow; Johna Rogersa (1998). „Ograniczenia złożoności obliczeń kwantowych” (PDF) . arXiv : cs/9811023 . Bibcode : 1998cs.......11023F . {{ cite journal }} : Cite journalwymaga |journal= ( pomoc ) Dostarcza informacji o powiązaniach pomiędzy różnymi klasami złożoności.
• Stephen A. Fenner (19 czerwca 2002). „PP-niskość i prosta definicja AWPP” . Kolokwium elektroniczne na temat złożoności obliczeniowej. {{ cite journal }} : Cite journal wymaga |journal= ( pomoc ) Definicja AWPP i połączenia z APP i PP.
• Lance Fortnow; John D. Rogers (12 listopada 1998). „Ograniczenia złożoności obliczeń kwantowych”. arXiv : cs/9811023 . Dowód BPQ w AWPP.
• „Klasy liczenia z możliwością definiowania przerw” autorstwa S. Fennera, L. Fortnowa i S. Kurtza z Journal of Computer and System Sciences . Strony 116–148, 1994, wydanie 48. Zawiera definicje.
• „Zestaw narzędzi budowniczego wyroczni” autorstwa S. Fennera, L. Fortnowa, S. Kurtza i L. Li. w materiałach z 8. struktury IEEE w teorii złożoności. Strony 120–131, 1993. Zawiera definicje.

Linki zewnętrzne

• „Zoo złożoności” zarchiwizowane 2018-12-01 w Wayback Machine : zawiera listę klas złożoności, w tym AWPP, oraz ich relacje z innymi klasami.