RP (complessità)

Nella teoria della complessità computazionale, RP (Randomized Polynomial time, "tempo polinomiale randomizzato") è la classe di complessità dei problemi decisionali eseguiti su una macchina di Turing probabilistica.

Si può inoltre definire una classe molto vicina: co-RP.

Definizione

Una prima definizione

La classe RP è l'insieme dei problemi, o in modo equivalente dei linguaggi, per i quali esiste una macchina di Turing probabilistica in tempo polinomiale che soddisfa le seguenti condizioni di accettazione:

  • Se la parola non è nel linguaggio, la macchina la rifiuta.
  • Se la parola è nel linguaggio, la macchina l'accetta con una probabilità superiore a 1/2.

Si dice che la macchina "sbaglia solo da un lato".

Definizione formale

Per un polinomio con dimensione dell'input , si definisce , l'insieme dei linguaggi per i quali esiste una macchina di Turing probabilistica , nel tempo , tale che per ogni parola  :

  • .
  • .

Allora si può definire RP come: .

Il ruolo della costante

La costante 1/2 è in realtà arbitraria, si può scegliere qualsiasi numero (costante) tra 0 e 1 (esclusi)[1].

L'idea è che eseguendo il calcolo indipendentemente un numero polinomiale di volte , si può ridurre la probabilità di errore a nel caso in cui (pur conservando una risposta sicura nel caso ).

La classe co-RP

La classe co-RP è l'insieme di linguaggi per i quali esiste una macchina di Turing probabilistica in tempo polinomiale che soddisfa le seguenti condizioni di accettazione:

  • Se la parola è nel linguaggio, la macchina l'accetta.
  • Se la parola non è nel linguaggio, la macchina lo rifiuta con una probabilità superiore a 1/2.

(Stessa osservazione per la costante.)

Relazioni con le altre classi

Con le classi "classiche"

Si ha la relazione seguente con le classi P e NP:

Osserviamo che questa classe non è più interessante se P=NP.

Con le altre classi probabilistiche

Inclusioni di classi di complessità probabilistiche

Le inclusioni seguenti mettono in gioco le classi ZPP e BPP.

Questo discende direttamente dalle definizioni: ZPP è l'intersezione di RP e di co-RP e BPP con condizioni di accettazione meno stringenti (errore "dai due lati").

Problemi in RP e co-RP

Quelli di RP sono problemi per i quali esiste un algoritmo probabilistico che soddisfa le condizioni descritte sopra.

Per esempio il problema di sapere se un numero intero è primo è nella classe di complessità co-RP grazie al test di primalità di Miller-Rabin. Infatti, questo problema è lo stesso in P, grazie al test di primalità AKS.

Un problema di co-RP che non è conosciuto essere in P è il problema della "verifica dell'identià ponomiale" (polynomial identity testing), che consiste, dato un polinomio multivariato sotto una qualsiasi forma, nel decidere se esso è identicamente nullo o no. Grazie al lemma di Schwartz–Zippel, si possono riconoscere i polinomi nulli con una buona probabilità valutandoli in un piccolo numero di punti.

Storia

La classe di complessità RP fu introdotta da John Gill[2] nell'articolo Computational complexity of probabilistic Turing machines (Gill (1977)).

Note

  1. ^ Arora & Barak (2009), capitolo 7.
  2. ^ Complexity Zoo, su complexityzoo.uwaterloo.ca. URL consultato il 12 marzo 2014 (archiviato dall'url originale il 21 luglio 2017).

Bibliografia

Collegamenti esterni

  Portale Informatica

Read other articles:

Bertus Caldenhove

Bertus Caldenhove Informasi pribadiTanggal lahir (1914-01-19)19 Januari 1914Tempat lahir Amsterdam, BelandaTanggal meninggal 30 Juli 1983(1983-07-30) (umur 69)Posisi bermain BekKarier senior*Tahun Tim Tampil (Gol) Door Wilskracht Sterk Tim nasional1935-1940[1] Belanda 25 (0) * Penampilan dan gol di klub senior hanya dihitung dari liga domestik Bernardus Joannes Caldenhove (19 Januari 1914 – 30 Juli 1983) adalah bek sepak bola Belanda yang bermain untuk Belanda di...

 

Robert Gallo

American biomedical researcher Robert GalloBornRobert Charles Gallo (1937-03-23) March 23, 1937 (age 86)Waterbury, Connecticut, United StatesEducationProvidence College (BS)Thomas Jefferson University (MD)Years active1963–presentKnown forCo-discoverer of HIVMedical careerProfessionMedical doctorInstitutionsNational Cancer InstituteSub-specialtiesInfectious disease and virologyResearchBiomedical researchAwardsLasker Award (1982, 1986)Charles S. Mott Prize (1984)Dickson Prize (...

 

Adel, Georgia

Adel, GeorgiaKotaAdel City Hall, 2012Lokasi di Cook County dan negara bagian GeorgiaNegara Amerika SerikatNegara bagianGeorgiaCountyCookLuas • Total82 sq mi (21,3 km2) • Luas daratan81 sq mi (20,9 km2) • Luas perairan2 sq mi (0,5 km2)Ketinggian240 ft (73 m)Populasi (2010)[1] • Total5.334 • Kepadatan6,620/sq mi (255,6/km2)Zona waktuUTC-5 (Eastern (EST)) ...

Sejarah Svalbard

Kepulauan kutub Svalbard pertama kali ditemukan oleh Willem Barentsz pada tahun 1596, meskipun terdapat bukti sengketa penggunaan oleh Pomors atau suku Nordik. Perburuan paus-paus bowhead dimulai pada tahun 1611, yang didominasi oleh perusahaan Inggris dan Belanda, dan negara-negara lain yang juga berpartisipasi. Saat itu belum ada kesepakatan mengenai kedaulatan. Stasiun perburuan paus, yang terbesar adalah Smeerenburg yang dibangun pada abad ke-17. Secara bertahap perburuan paus menurun. Pe...

 

Luis Larrea Alba

In this Spanish name, the first or paternal surname is Larrea and the second or maternal family name is Alba. Luis Larrea AlbaActing President of EcuadorIn office24 August 1931 – October 15 1931Preceded byIsidro AyoraSucceeded byAlfredo Baquerizo Personal detailsBorn(1894-10-25)25 October 1894Guayaquil, EcuadorDied17 April 1979(1979-04-17) (aged 84)Córdoba, ArgentinaPolitical partyRadical Liberal Luis Alberto Larrea Alba (25 October 1894, Guayaquil, Ecuador – 17...

 

News media in the United States

American reporting on current events American Journalism redirects here. For the academic journal, see American Journalism Historians Association. This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources:&#...

Hubungan Brasil dengan Jepang

Hubungan Brasil–Jepang Brasil Jepang Tanda persahabatan di Maringa, Brasil Distrik Liberdade, São Paulo adalah kota Jepang terbesar di dunia. Hubungan Brasil–Jepang merujuk kepada hubungan bilateral Brasil dan Jepang. Jepang pertama kali membangun hubungan diplomatik dengan Brasil pada 1895.[1] Jepang menggunakan hubungan luar negeri untuk mempromosikan perdagangannya dengan Brasil setelah PD2.[2] Investasi langsung digunakan untuk mengembangkan bisnis di Brasil.[3&#...

 

List of deputy chief ministers of Haryana

Deputy Chief Minister of Haryanaहरियाणा के उपमुख्यमंत्रीEmblem of HaryanaIncumbentVacantsince 12 March 2024StyleThe HonourableStatusDeputy Head of GovernmentAbbreviationDCMMember ofHaryana Legislative AssemblyResidence48, Sector 2, ChandigarhSeatChandigarhAppointerGovernor on the advice of the Chief MinisterInaugural holderChand RamFormation24 March 1967 The Deputy Chief Minister of Haryana (DCMO Haryana)[1] is a member of the Cabinet ...

 

Lapangan Panahan Gelora Bung Karno

Lapangan Panahan Gelora Bung KarnoLapangan Panahan GBK, Lapangan Panahan SenayanInformasi stadionPemilikKementerian Sekretariat Negara Republik IndonesiaOperatorPusat Pengelolaan Kompleks Gelora Bung KarnoLokasiLokasi Gelora, Tanah Abang, Jakarta Pusat, DKI Jakarta, IndonesiaKonstruksiDibuat2016Dibuka2 November 2017Data teknisKapasitas97Situs web[1]Sunting kotak info • L • BBantuan penggunaan templat ini Lapangan Panahan Gelora Bung Karno adalah sebuah Lapangan panahan di Jakart...

Greesella Adhalia

Greesella AdhaliaLahirGreesella Sophina Adhalia10 Januari 2006 (umur 18)Bogor, Jawa Barat, IndonesiaKebangsaanIndonesiaPekerjaanAktrismodelpenyanyipenariTahun aktif2016—sekarangKarier musikGenrePopJ-popInstrumenVokalLabelIndonesia Musik Nusantara (2022-sekarang)AnggotaJKT48 (2022-sekarang) Greesella Sophina Adhalia (lahir 10 Januari 2006) adalah pemeran, model, penyanyi, dan penari Indonesia. Greesel merupakan anggota JKT48 generasi ke-11 yang diperkenalkan pada 31 Oktober 2022. ...

 

Ю

Cette page contient des caractères spéciaux ou non latins. S’ils s’affichent mal (▯, ?, etc.), consultez la page d’aide Unicode. Iou Graphies Capitale Ю Bas de casse ю Utilisation Alphabets Cyrillique Ordre 32e Phonèmes principaux /ju/, /u/, /y/ modifier  Les formes du you dans l’Alphabet de Karion Istomin de 1694. Iou (capitale Ю, minuscule ю) est la 32e et avant-dernière lettre de l'alphabet cyrillique. Elle sert parfois à accueillir des mots issus de la l...

 

Polk County, North Carolina

County in North Carolina, United States County in North CarolinaPolk CountyCountyPolk County Courthouse FlagSealLocation within the U.S. state of North CarolinaNorth Carolina's location within the U.S.Coordinates: 35°17′N 82°10′W / 35.28°N 82.17°W / 35.28; -82.17Country United StatesState North CarolinaFounded1855Named forColonel William PolkSeatColumbusLargest municipalityTryonArea • Total238.45 sq mi (617.6 km2) •&#...

24K Magic (song)

2016 single by Bruno Mars 24K MagicR3hab remix cover artSingle by Bruno Marsfrom the album 24K Magic ReleasedOctober 7, 2016 (2016-10-07)Recorded2015–16StudioGlenwood Place (Burbank, California)Genre Funk disco R&B Length3:45LabelAtlanticSongwriter(s) Bruno Mars Philip Lawrence Christopher Brody Brown Producer(s) Shampoo Press & Curl The Stereotypes (add.) Bruno Mars singles chronology Uptown Funk (2014) 24K Magic (2016) That's What I Like (2017) Music video24K Magic ...

 

Famille Upori

Upori Armoiries de la famille Upori Blasonnement D’azur, au dextrochère d'argent armé d'un sabre de même, soutenu d'une couronne, accompagnée en chef senestre de deux roses de gueules en pal Lignées Clan Akus Pays ou province d’origine  Royaume de Hongrie Allégeance au roi de Hongrie puis au roi d'Autriche modifier  La famille Upori (aussi Upory) est une famille noble hongroise[1]. Histoire La famille Upori est issue de l'ancien clan hongrois Akus. En 1435, un document no...

 

Académie d'agriculture de France

Pour les articles homonymes, voir AAF. Ne doit pas être confondu avec Société nationale d'horticulture de France. Académie d'agriculture de France Son « ambition est connaître » et sa « passion transmettre »HistoireFondation 1761Prédécesseur Société nationale d'agriculture de France (d)CadreSigle AAFType Société savanteDomaine d'activité alimentation, agriculture, environnementSiège Paris (18, rue de Bellechasse, 75007)Pays  FranceCoordonnées 48°&#...

Gerad Parker

American football player and coach (born 1981) Not to be confused with Gerald Parker or Gerard Parker. Gerad ParkerCurrent positionTitleHead coachTeamTroyConferenceSun BeltRecord0–0Biographical detailsBorn (1981-01-04) January 4, 1981 (age 43)[1]Huntington, West Virginia, U.S.Playing career2000–2004Kentucky Position(s)Wide receiverCoaching career (HC unless noted)2005–2006Raceland-Worthington HS (KY) (WR/DB)2007Kentucky (GA)2008–2010UT Martin (PGC/RC)2011–2012Marshall (...

 

Instituto de Investigación Grantham sobre Cambio Climático y Medio Ambiente

No debe confundirse con Instituto Grantham - Cambio Climático y Medio Ambiente. Edificio principal de la Escuela de Economía y Ciencia Política de Londres (LSE), en la que se fundó el Instituto de Investigación Grantham sobre Cambio Climático y Medio Ambiente. El Instituto de Investigación Grantham sobre Cambio Climático y Medio Ambiente (GRICCE por sus siglas en inglés, como las de todas las instituciones que se mencionan a continuación) es un organismo de investigación, fundado e...

 

Badai Tropis Khanun (2012)

Untuk kegunaan lain, lihat Topan Khanun. Badai Tropis Khanun (Enteng)Badai tropis parah (skala JMA)Badai tropis (SSHWS)Badai Tropis Khanun (Enteng) setelah intensitas puncak, mendekati daratan Korea pada tanggal 18 JuliTerbentuk pada14 Juli 2012Mereda pada20 Juli 2012 (Menjadi siklon Extratropical pada tanggal 19 Juli) Kecepatan anginmaksimal10 menit: 95 km/jam 1 menit: 95 km/jam Tekanan minimal985 hPa (mbar) Korban jiwa9 dilaporkan (1 di Korea Selatan, 8 di Korea Utara)Kerusakan11.4 jut...

Arabs in Berlin

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. (June 2012) (Learn how and when to remove this message) Ethnic group Arabs in Berlinالعرب في برلينTotal populationEstimated at around 135,000[1] (3.5%)Regions with significant populationsBerlin Neukölln, Schöneberg, Gesundbrunnen, Moabit, KreuzbergLanguagesGerman · ArabicReligi...

 

بلقيس

  لمعانٍ أخرى، طالع بلقيس (توضيح). بلقيس (بالعبرية: מלכת שְׁבָא)‏  ملكة مملكة سبأ الملكة بلقيس، مخطوطة من القرن الخامس عشر، موجودة في مكتبة الولاية والجامعة غوتنغن. معلومات شخصية الميلاد القرن 10 ق.م  تاريخ الوفاة القرن 10 ق.م  الإقامة مملكة سبأ  العشير سليمان ...