MA (Complexitat)

En teoria de la complexitat, la classe de complexitat MA és el conjunt dels problemes de decisió que poden ser resolts en temps polinòmic per un protocol Arthur-Merlin d'un sol missatges. Només hi ha un missatge: Merlin envia un missatge a Arthur i aquest decideix si accepta o no executant un computació probabilística en temps polinòmic. En aquesta classe Merlín no té accés als resultats dels llançaments de moneda d'Arthur, ja que fa el llançament després de rebre el missatge de Merlin.[1][2]

Per tant, un llenguatge L és a MA si existeix una màquina de Turing determinista de temps polinòmic M i uns polinomis p i q tals que per cada cadena d'entrada x de longitud n = |x|,

  • si x és a L, llavors
  • si x no és a L, llavors

La segona condició es pot escriure d'aquesta forma alternativa:

  • si x no és a L, llavors

on z és la prova que envia Merlin (de mida polinòmica) i y és la cadena aleatòria que utilitza l'Arthur, que també està fitada polinòmicament.

Relació amb d'altres classes

La classe MA està contingut dins de les classes AM i QMA.

No se sap si les classes MA i AM son diferents, segons certes condicions les dues son equivalents a la classe NP.[3]

MA conté les classes NP i BPP.

Referències

  1. ↑ Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
  2. ↑ «Complexity Zoo:M - Complexity Zoo» (en anglès). Arxivat de l'original el 2017-10-16. [Consulta: 3 desembre 2018].
  3. ↑ Impagliazzo, Russell; Wigderson, Avi «P = BPP if E requires exponential circuits: derandomizing the XOR lemma». Proceeding STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM, 04-05-1997, pàg. 220–229. DOI: 10.1145/258533.258590.

Read other articles:

12 Sweet Memories Panbers

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: 12 Sweet Memories Panbers – berita · surat kabar · buku · cendekiawan · JSTOR Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan...

 

Budaya Taiwan

Kebudayaan Taiwan adalah suatu campuran dari kebudayaan Tionghoa Han Konfusianis dan penduduk asli Taiwan, yang sering dipersepsikan baik dalam pemahaman tradisional maupun modern.[1] Pengalaman sosial-politik umum di Taiwan secara bertahap berkembang menjadi kepekaan terhadap identitas budaya Taiwan dan perasaan kesadaran budaya Taiwan, yang telah diperdebatkan secara luas di dalam negeri.[2][3][4] Merefleksikan kontroversi yang terus berlanjut yang menyelimut...

 

Johnnie Walker

Johnnie WalkerJenismerek, Wiski Skotch, Wiski, whisky distillery (en), produk dan alcohol brand (en) AsalSkotlandiaDiperkenalkan1820: Grocery store 1865: Scotch blendingDihentikanWhite LabelProdusenDiageo80VarianRed Label, Black Label, Swing, Green Label, Gold Label, Blue LabelSitus webhttps://www.johnniewalker.com/es-uy dan https://www.johnniewalker.com/ [sunting di Wikidata]lbs Black Label, Limited edition for F1 team McLaren Mercedes Johnnie Walker ad...

De Bouwploeg

N.V. de BouwploegKantor pusat de Bouwploeg di Nieuw-GondangdiaJenisNaamloze vennootschapIndustriLahan yasanNasibBangkrut setelah pendirinya meninggalDidirikan1912 (1912) di Gondangdia, Batavia, Hindia BelandaPendiriPieter Adriaan Jacobus MoojenDitutup1918 (1918)KantorpusatBatavia, Hindia Belanda N.V. de Bouwploeg (pengucapan Melayu Betawi: Boplo) adalah perusahaan real estat pertama di Hindia Belanda yang didirikan pada tahun 1912 oleh arsitek Pieter Adriaan Jacobus Moojen guna men...

 

Friedrich Ludwig dari Hohenlohe-Ingelfingen

Frederick Louis, Pangeran Hohenlohe-Ingelfingen Frederick Louis, Pangeran Hohenlohe-Ingelfingen (Jerman: Friedrich Ludwig Fürst zu Hohenlohe-Ingelfingencode: de is deprecated ) (31 Januari 1746 – 15 Februari 1818) adalah jendral Prusia dan putra tertua Pangeran John Frederick (Johann Friedrich; meninggal 1796) dari Hohenlohe-Ingelfingen. Frederick Louis meninggal di Slawentzitz. Referensi  Artikel ini menyertakan teks dari suatu terbitan yang sekarang berada pada ra...

 

Johnson County, Missouri

County in Missouri, United States County in MissouriJohnson CountyCountyJohnson County Courthouse in WarrensburgLocation within the U.S. state of MissouriMissouri's location within the U.S.Coordinates: 38°45′N 93°49′W / 38.75°N 93.81°W / 38.75; -93.81Country United StatesState MissouriFoundedDecember 13, 1833Named forRichard Mentor JohnsonSeatWarrensburgLargest cityWarrensburgArea • Total833 sq mi (2,160 km2) • L...

How to Buy a Friend

How to Buy a FriendPoster promosiHangul계약우정 GenreSekolahBeranjak dewasaDramaRomansaBerdasarkanContract Friendshipoleh Kwon LaadDitulis olehKim Joo-manSutradaraYoo Young-eunPemeranLee Shin-youngShin Seung-hoKim So-hyeNegara asalKorea SelatanBahasa asliKoreaJmlh. episode8ProduksiProduser eksekutifMoon Joon-ha Kim Yong-jinSohn Jae-sungPengaturan kameraSingle-cameraRumah produksiMega MonsterDistributorKBSRilis asliJaringanKBS2Format audioDolby DigitalRilis6 April (2020-04-06) �...

 

Eleventh Dynasty of Egypt

Group of rulers in ancient Egypt Eleventh Dynasty of Egyptc. 2150 BC–c. 1991 BCFunerary stele of Intef II, on display at the Metropolitan Museum of Art.CapitalThebesCommon languagesEgyptian languageReligion ancient Egyptian religionGovernmentAbsolute monarchyHistorical eraBronze Age• Established c. 2150 BC• Disestablished c. 1991 BC Preceded by Succeeded by Tenth Dynasty of Egypt Twelfth Dynasty of Egypt Periods and dynasties of ancient Egypt All y...

 

Lampung pada Pekan Olahraga Nasional 2021

Lampung pada Pekan Olahraga Nasional 2021 Jumlah atlet 138 di 28 cabang olahraga Pembawa bendera TBD Total medali Emas Perak Perunggu   (Urutan ke- ) Lampung akan berkompetisi pada Pekan Olahraga Nasional 2021 di Jayapura, Papua. Sebenarnya kontingen ini dijadwalkan untuk bertanding pada 20 Oktober sampai 2 November 2020 namun ditunda ke tanggal 2 sampai 15 Oktober 2021 karena Pandemi COVID-19.[1] Jumlah atlet Cabang olahraga Putra Putri Total Angkat berat 4 5 9 Angkat besi...

Ludovico di Varthema

Laman judul Belanda dari buku Varthema Itinerario, 1654 Ludovico di Varthema, juga dikenal sebagai Barthema dan Vertomannus (s. 1470 – 1517), adalah seorang penjelajah, pembuat buku harian dan aristokrat Italia yang dikenal karena menjadi salah satu orang Eropa non-Muslim pertama yang memasuki Makkah sebagai seorang peziarah. Nyaris setiap hal yang diketahui tentang hidupnya berasal dari catatan perjalanannya sendiri, Itinerario de Ludouico de Varthema Bolognese, yang diterbitkan di Roma pa...

 

Fulvio Zuccheri

Fulvio Zuccheri Nazionalità  Italia Altezza 177 cm Peso 72 kg Calcio Ruolo Allenatore (ex difensore, centrocampista) Termine carriera 1990 - giocatore Carriera Giovanili 1967-1971 S.P. Aiello1971-1975 Udinese Squadre di club1 1974-1975 Udinese1 (0)1975-1979 Cesena22 (1)1979-1982 Bologna57 (1)1982-1983 Reggiana33 (0)1983-1984 Cremonese22 (0)1984-1986 Pistoiese41 (2)1986-1988 Campania Puteolana45 (0)1988-1990 Sassuolo49 (0)1990-1991 Pro V...

 

Anarchism in Norway

Part of a series onAnarchism History Outline Schools of thought Feminist Green Primitivist Social ecology Total liberation Individualist Egoist Free-market Naturist Philosophical Mutualism Postcolonial African Black Queer Religious Christian Jewish Social Collectivist Parecon Communist Magonism Without adjectives Methodology Agorism Illegalism Insurrectionary Communization Expropriative Pacifist Platformism Especifismo Relationship Syndicalist Synthesis Theory Practice Anarchy Anarchist Blac...

Mahabubabad district

District of Telangana in IndiaMahabubabad districtDistrict of TelanganaEpiphany Cathedral, DornakalLocation in TelanganaMahabubabad districtCountryIndiaStateTelanganaHeadquartersMahabubabadMandalas16Government • District collectorSri V.P.Goutham • Parliament constituenciesMahabubabad • Assembly constituenciesMahabubabad, DornakalArea • Total2,876.70 km2 (1,110.70 sq mi)Population (2011) • Total774,549 •...

 

Mario Camus

Mario Camus (2011). Mario Camus (Santander, 20 aprile 1935 – Santander, 17 settembre 2021[1]) è stato un regista e sceneggiatore spagnolo. Indice 1 Biografia 2 Filmografia 3 Note 4 Bibliografia 5 Collegamenti esterni Biografia Studiò diritto e successivamente frequentò la Escuela Oficial de Cine. Camus appartiene alla generazione del Nuevo Cine Español, della quale fanno parte, tra gli altri, Carlos Saura, Basilio Martín Patino, José Luis Borau, Julio Diamante, Miguel Picazo e...

 

土库曼斯坦总统

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府（Oguzkhan Presidential Palace）機關所在地阿什哈巴德任命者直接选举任期7年，可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日 土库曼斯坦土库曼斯坦政府与政治 国家政府 土库曼斯坦宪法 国旗 国徽 国歌 立法機關（英语：National Council of Turkmenistan） ...

Sierra Leone aux Jeux olympiques d'été de 2008

Cet article est une ébauche concernant les Jeux olympiques et la Sierra Leone. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Sierra Leone aux Jeux olympiques d'été de 2008 Code CIO SLE Lieu Pékin Participation 8e Athlètes 3 dans 2 sports Porte-drapeau Solomon Bayoh MédaillesRang : Or0 Arg.0 Bron.0 Total0 Sierra Leone aux Jeux olympiques d'été Sierra Leone aux Jeux olympiques d'été de 2004 Sierra...

 

Colt Dragoon Revolver

1848 revolver by Samuel Colt Colt Dragoon Revolver Third Model Dragoon, U.S. Cavalry issuedTypeRevolverPlace of originUnited StatesService historyIn service1848–1865Used byUnited StatesWarsAmerican Indian Wars, American Civil WarProduction historyDesignerSamuel ColtDesigned1848–1850ManufacturerColt FirearmsProduced1848–1860No. builtAbout 18,500 in U.S.A.VariantsWalker Transitions, First and Second ModelsSpecificationsMass4 pounds 4 ounces (1.9 kg)...

 

North Carolina Cabinet

Group of unelected heads of the executive departments of the Government of North Carolina Not to be confused with North Carolina Council of State. The North Carolina Cabinet is the group of unelected heads of the executive departments of the Government of North Carolina. It is separate and distinct from the North Carolina Council of State, the members of which are elected statewide, and which makes up the rest of the executive leadership of the government. All cabinet secretaries are appointe...

The Show-Off (1934 film)

1934 film by Charles Reisner The Show-OffLobby cardDirected byCharles ReisnerWritten byHerman J. MankiewiczBased onThe Show-Offby George KellyProduced byLucien HubbardStarringSpencer Tracy Madge Evans Henry WadsworthCinematographyJames Wong HoweEdited byWilliam S. GrayProductioncompanyMetro-Goldwyn-MayerDistributed byMetro-Goldwyn-MayerRelease date March 9, 1934 (1934-03-09) Running time77 minutesCountryUnited StatesLanguageEnglishBudget$162,000[1][2]Box office$...

 

Jarrod Bleijie

Australian politician Jarrod BleijieMP, JPBleijie, 2017Deputy Leader of the Opposition in QueenslandIncumbentAssumed office 14 March 2022PremierAnnastacia PalaszczukSteven MilesLeaderDavid CrisafulliPreceded byDavid JanetzkiDeputy Leader of the Liberal National PartyIncumbentAssumed office 14 March 2022LeaderDavid CrisafulliPreceded byDavid Janetzki Shadow cabinet positions Shadow Minister for FinanceIncumbentAssumed office 16 November 2020LeaderDavid CrisafulliPreceded byPosition...