Класс PP

В теории сложности, PP является классом проблем, решаемых вероятностными машинами Тьюринга за полиномиальное время, с вероятностью ошибки менее 1/2. Аббревиатура PP обозначает «вероятностный полиномиальный по времени».

Определение

Язык L принадлежит PP тогда и только тогда, когда существует вероятностная машина Тьюринга M такая, что

M полиномиальна по времени
Для любого x из L, M возвращает 1 с вероятностью строго большей 1/2
Для любого x не из L, M возвращает 1 с вероятностью не большей 1/2

PP и BPP

Класс BPP является подмножеством класса PP; его можно рассматривать как подмножество задач, для которых имеются эффективные вероятностные алгоритмы. Разница заключается в величине вероятности ошибки: в классе BPP, любой алгоритм должен дать правильный ответ с вероятностью больше, чем c (с > 1/2), например 2/3 или 777/1000. В этом случае, можно запустить алгоритм фиксированное количество раз, а затем выбрать ответ, имеющий большинство голосов, чтобы достигнуть определенной вероятности корректности меньше 1. Количество повторений увеличивается при приближении c к 1/2, но не зависит от n.

Замечание. c не может зависеть от входа. С другой стороны, алгоритм из PP может проделывать следующую последовательность действий:

Если правильный ответ «Да», алгоритм говорит «Да» с вероятностью 1/2+1/2ⁿ, где n — это длина входа.
Если правильный ответ «Нет», алгоритм говорит «Да» с вероятностью 1/2-1/2ⁿ.

Так как эти две возможности достаточно близки, в особенности для больших n, даже если машина Тьюринга будет запущена большое количество раз очень сложно понять, работаем ли мы с вариантом, где правильный ответ «Да» или «Нет». Попытка добиться фиксированного значения вероятности, используя большинство голосов, требует количество повторений, экспоненциальное по n. Грубо, это можно сравнить с задачей определения, какой стороной выпадет монетка с небольшим перевесом, подбрасывая её большое количество раз.

Классы сложности алгоритмов
Считаются лёгкими	DLOGTIME^[англ.] AC⁰^[англ.] ACC⁰^[англ.] TC⁰^[англ.] L SL^[англ.] RL^[англ.] NL NC SC^[англ.] CC^[англ.] P P-complete^[англ.] ZPP RP BPP BQP EQP APX
Предполагаются сложными	UP^[англ.] NP NP-complete co-NP co-NP-complete AM^[англ.] MA^[англ.] QMA PH ⊕P^[англ.] PP #P #P-complete^[англ.] IP^[англ.] PSPACE PSPACE-complete^[англ.]
Считаются сложными	EXPTIME NEXPTIME^[англ.] EXPSPACE^[англ.] 2-EXPTIME^[англ.] ELEMENTARY^[англ.] R PR^[англ.] RE^[англ.] RE-complete^[англ.] Co-RE^[англ.] Co-RE-complete^[англ.] ALL^[англ.]

В статье не хватает ссылок на источники (см. рекомендации по поиску).

Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (20 октября 2024)

Read other articles:

Pemilihan umum Bupati Merangin 2013

Pemilihan umum Bupati Merangin 20132008201825 Maret 2013[1]Kandidat Calon Nalim Syukur Handayani Partai Demokrat PAN PKB Pendamping Salam Fauziah Jailani Suara rakyat 49.519 47.678 22.576 Persentase 25.50% 24.49% 11.62% Calon Al Haris Partai Golkar Pendamping Abdul Khafidh Suara rakyat 71.059 Persentase 36.59% Peta persebaran suara Letak Kabupaten Merangin di Provinsi Jambi Bupati petahanaNalim Demokrat Bupati terpilih Al Haris Golkar Pemilihan umum Bupati Mer...

Pengelatan

Contoh sebuah senyawa kelat: Ligan etilenadiamina mengkelat pada suatu atom logam dengan dua ikatan berlokasi berbeda. Dalam kimia koordinasi, pengkelatan (atau penyapitan, Inggris: chelation)[1] adalah pengikatan suatu atom dengan suatu ligan yang mengikatnya pada dua atau lebih lokasi ikatan (seolah-olah menjepit atom pusat tersebut). Senyawa yang memiliki ikatan demikian disebut senyawa kelat.[1] Umumnya atom yang dijepit adalah atom logam dan ligannya adalah senyawa organi...

Roubaix

RoubaixBalai kota Koordinat: 50°41′24″N 3°10′54″E / 50.69°N 3.18167°E / 50.69; 3.18167NegaraPrancisArondisemenLilleKantonKota utama dari 2 kantonAntarkomuneMétropole européennede LillePemerintahan • Wali kotaGuillaume Delbar (UMP)Kode INSEE/pos59512 / Gereja paroki Santo Martinus Roubaix (bahasa Belanda Robaais) ialah sebuah kota di Nord, Prancis utara, dekat kota Lille dan Tourcoing serta perbatasan Belgia. Pemandangan Yang paling utama...

Vladivostok

Vladivostok ВладивостокPemandangan Kota Vladivostok dan Teluk Tanduk Emas BenderaLambang kebesaranPeta lokasi Vladivostok VladivostokLokasi VladivostokTampilkan peta RusiaVladivostokVladivostok (Primorsky Krai)Tampilkan peta Primorsky KraiKoordinat: 43°7′N 131°54′E / 43.117°N 131.900°E / 43.117; 131.900Koordinat: 43°7′N 131°54′E / 43.117°N 131.900°E / 43.117; 131.900NegaraRusiaSubjek federalPrimorsky KraiPendirian2 Jul...

دونكيرك (نيويورك)

لمعانٍ أخرى، طالع دونكيرك (توضيح). دونكيرك الإحداثيات 42°28′46″N 79°20′02″W / 42.479444444444°N 79.333888888889°W / 42.479444444444; -79.333888888889 [1] تاريخ التأسيس 1880 تقسيم إداري البلد الولايات المتحدة[2][3] التقسيم الأعلى مقاطعة تشاتوكوا خصائص جغرافية ...

Another Woman (film 1988)

Untuk film Taiwan, lihat Another Woman (film 2015). Another WomanPoster rilis teatrikalSutradaraWoody AllenProduserRobert GreenhutDitulis olehWoody AllenPemeran Philip Bosco Betty Buckley Blythe Danner Sandy Dennis Mia Farrow Gene Hackman Ian Holm John Houseman Martha Plimpton Gena Rowlands David Ogden Stiers Harris Yulin SinematograferSven NykvistPenyuntingSusan E. MorseDistributorOrion PicturesTanggal rilis 14 Oktober 1988 (1988-10-14) Durasi77 menitNegaraAmerika SerikatBahasaInggrisPe...

العلاقات الإيرانية السيشلية

العلاقات الإيرانية السيشلية إيران سيشل إيران سيشل تعديل مصدري - تعديل العلاقات الإيرانية السيشلية هي العلاقات الثنائية التي تجمع بين إيران وسيشل.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة إيران سيشل �...

Saori Hara

Saori HaraHara di Festival Film Internasional Tokyo 2017Nama asal原紗央莉LahirMai Kato1 Januari 1988 (umur 36)[1]Hiroshima, JepangTinggi165 m (541 ft 4 in)Situs webhttp://blog.livedoor.jp/harasaori/ Saori Hara (Jepang: 原紗央莉code: ja is deprecated , Hepburn: Hara Saori, lahir 1 Januari 1988) adalah seorang mantan idola film dewasa, peraga busana dan pemeran asal Jepang yang memakai nama Mai Nanami (七海まいcode: ja is deprecated , Nanami Mai)...

Marcus Vipsanius Agrippa

Roman general and statesman (c. 63–12 BC) Marcus Vipsanius AgrippaBust of Agrippa in the Louvre, Paris, ca. 25–24 BC.Bornc. 63 BC[1]Uncertain location, possibly Arpino, Istria or Asisium,[2] Roman RepublicDied12 BC (aged 50–51)Campania, Roman Italy, Roman EmpireResting placeMausoleum of AugustusNationalityRomanOccupation(s)Military commander, politicianNotable workPantheon (original)OfficeConsul (37, 28–27 BC)Spouses Caecilia Attica, Claudia Marcella Maior, Julia...

Marco Antônio de Mattos Filho

Marquinho Marquinho con la maglia della Roma Nazionalità Brasile Altezza 182[1] cm Peso 79[1] kg Calcio Ruolo Centrocampista, ala Termine carriera 12 agosto 2021 Carriera Giovanili 1998-1999 Caxias1999-2000 Juventude2000 Internacional2000-2001 Grêmio2001 Vasco da Gama2001-2006 Palmeiras Squadre di club1 2006-2007 Palmeiras1 (0)2007 Botafogo5 (0)2008 Figueirense27 (5)2009-2011 Fluminense94 (9)[2]2012-2014 R...

Henry Fuseli

Swiss-born British painter, draughtsman and writer on art (1741–1825) Henry FuseliRAHenry Fuseli, 1778. Portrait by James Northcote.BornJohann Heinrich Füssli(1741-02-07)7 February 1741Zürich, SwitzerlandDied17 April 1825(1825-04-17) (aged 84)Putney Hill, London, EnglandNationalitySwissKnown forPainting, draughtsmanshipNotable workThe NightmareMovementRomanticismSpouse Sophia Rawlins (m. 1788) Henry Fuseli RA (/ˈfjuːzəli, fjuːˈzɛli/ FEW-zə-l...

Gareth Edwards (director)

British filmmaker Not to be confused with Gareth Evans (director). Gareth EdwardsEdwards at the 2023 San Diego Comic-ConBorn (1975-07-13) 13 July 1975 (age 48)Nuneaton, Warwickshire, EnglandOccupationFilmmakerYears active2002–present Gareth James Edwards (born 13 July 1975) is an Welsh filmmaker. He gained recognition for Monsters (2010), an independent film in which he served as writer, director, cinematographer, and visual effects artist.[1][2] He subsequently di...

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

Giovanni di Paolo

Italian painter and illustrator of manuscripts (c.1403-1482) Not to be confused with Giovanni Paolo. Giovanni di Paolo, St Catherine of Siena Giovanni di Paolo di Grazia (c. 1403–1482) was an Italian painter, working primarily in Siena, becoming a prolific painter and illustrator of manuscripts, including Dante's texts. He was one of the most important painters of the 15th century Sienese School. His early works show the influence of earlier Sienese masters, but his later style was more ind...

Maria Miller

British politician (born 1964) For the Canadian artist, see Maria Morris Miller. The subject of this article is standing for re-election to the House of Commons of the United Kingdom on 4 July, and has not been an incumbent MP since Parliament was dissolved on 30 May. Some parts of this article may be out of date during this period. Please feel free to improve this article (but note that updates without valid and reliable references will be removed) or discuss changes on the talk pa...

Roberta Wohlstetter

American academic (1912–2007) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (March 2013) (Learn how and when to remove this message) Wohlstetter in 1985 Roberta Morgan Wohlstetter (August 22, 1912 – January 6, 2007) was an American historian of U.S. military intelligence. In 1962 she authored Pearl Harbor: Warning and Decision.[1] The book was based on a...

Benevento

Disambiguazione – Se stai cercando altri significati, vedi Benevento (disambigua). Beneventocomune Benevento – Vedutain senso orario in alto a destra: L'Arco di Traiano, la Basilica della Madonna delle Grazie, La Chiesa Longobarda di Santa Sofia, il Teatro Romano e la Villa dei Papi LocalizzazioneStato Italia Regione Campania Provincia Benevento AmministrazioneSindacoClemente Mastella (Noi Campani) dal 20-6-2016 (2º mandato dal 22-10-2021) TerritorioCoor...

Gliese 581 d

Gliese 581 d Gliese 581 d (pengucapan: /ˈgliːzə/) adalah planet ekstrasurya sejauh 20 tahun cahaya di rasi bintang Libra. Karena massanya, planet ini diklasifikasikan sebagai planet bumi super. Karena orbit planet ini berada di ujung luar zona laik huni bintangnya, planet ini diduga mirip dengan bumi. Pranala luar Wikimedia Commons memiliki media mengenai Gliese 581. Notes for planet Gl 581 d. The Extrasolar Planets Encyclopaedia. Diarsipkan dari versi asli tanggal 2007-09-26. Diakses tang...

Asuni

Asuni AsùniKomuneComune di AsuniLokasi Asuni di Provinsi OristanoNegaraItaliaWilayah SardiniaProvinsiOristano (OR)Pemerintahan • Wali kotaGionata PetzaLuas • Total21,34 km2 (8,24 sq mi)Ketinggian233 m (764 ft)Populasi (2016) • Total345[1]Zona waktuUTC+1 (CET) • Musim panas (DST)UTC+2 (CEST)Kode pos09080Kode area telepon0783Situs webhttp://comuneasuni.gov.it Asuni (bahasa Sardinia: Asùni) adalah sebuah komu...

Метательный заряд

Унитарный патрон.1 — снаряд (пуля), 2 — гильза, 3 — заряд пороха или иного взрывчатого вещества, 4 — донце гильзы и фланец, 5 — капсюль-воспламенитель.Картуз 12-дюймового орудия Mk.IX. Метательный заряд[1], Заряд[2], Боевой заряд[3] (Боезаряд) — определе...