Fonction parité

La fonction parité est une fonction booléenne. La sortie vaut 1, si et seulement si, le nombre de 1 dans l'entrée est impair. Un cas particulier est la fonction parité avec deux entrées, qui est connue sous le nom de XOR. Cette fonction est centrale dans l'étude des circuits booléens. Le résultat est parfois appelé bit de parité.

Circuits booléens

La fonction parité un exemple de fonction qui n'est pas dans la classe de complexité nommée AC0. Ceci a été démontré par Furst, Saxe et Sipser[1], et indépendamment à Miklós Ajtai[2].

Notes et références

  1. ↑ Merrick Furst, James B. Saxe et Michael Sipser, « Parity, circuits, and the polynomial-time hierarchy », Math. Syst. Theory, vol. 17,‎ , p. 13-27 (ISSN 0025-5661, DOI 10.1007/bf01744431, zbMATH 0534.94008)
  2. ↑ Miklós Ajtai, « ∑ 1 1-formulae on finite structures », Annals of pure and applied logic, vol. 24, no 1,‎ , p. 1-48

Read other articles:

Hana Yori Dango Final

Hana Yori Dango FinalPoster Hana Yori Dango Final di SingaporeNama lain花より男子ファイナル (Hana Yori Dango Fainarucode: ja is deprecated )SutradaraYasuharu IshiiProduserKatsuaki SetoguchiDitulis olehMikio SatakeYoko KamioBerdasarkanHana Yori Dangooleh Yoko KamioPemeranMao InoueJun MatsumotoShun OguriShota MatsudaTsuyoshi AbeNaratorMao InouePenata musikArashiAikoKousuke YamashitaSinematograferToshiyasu YamanakaPerusahaanproduksiToho Company Ltd.Tanggal rilis 28 Juni 200...

 

Charity Shield FA 1950

Charity Shield FA 1950TurnamenCharity Shield FA England World Cup XI FA Canadian Touring Team 4 2 Tanggal20 September 1950StadionStamford Bridge, London← 1949 1951 → Charity Shield FA 1950 adalah pertandingan sepak bola antara England World Cup XI dan FA Canadian Touring Team yang diselenggarakan pada 20 September 1950 di Stamford Bridge, London. Pertandingan ini merupakan pertandingan ke-28 dari penyelenggaraan Charity Shield FA. Pertandingan ini dimenangkan oleh England World Cu...

 

Ogasawara, Tokyo

Village in the Ogasawara Islands, Japan 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: Ogasawara, Tokyo – news · newspapers · books · scholar · JSTOR (March 2017) (Learn how and when to remove this template message) Village in Kantō, JapanOgasawara 小笠原村VillageThe main settlement on Chichijima FlagS...

Sariputta

Bagian dari seri tentangBuddhisme SejarahPenyebaran Sejarah Garis waktu Sidang Buddhis Jalur Sutra Benua Asia Tenggara Asia Timur Asia Tengah Timur Tengah Dunia Barat Australia Oseania Amerika Eropa Afrika Populasi signifikan Tiongkok Thailand Jepang Myanmar Sri Lanka Vietnam Kamboja Korea Taiwan India Malaysia Laos Indonesia Amerika Serikat Singapura AliranTradisi Buddhisme prasektarian Aliran Buddhis awal Mahāsāṃghika Sthaviravāda Aliran kontemporer Theravāda Mahāyāna Vajrayāna Kon...

 

Austro-Tai languages

Proposed language family Austro-Tai(proposed)GeographicdistributionSoutheast Asia, East AsiaLinguistic classificationproposed language familySubdivisions Austronesian Kra–Dai Japonic (rarely included) GlottologNone The Austro-Tai languages, sometimes also Austro-Thai languages, are a proposed language family that comprises the Austronesian languages and the Kra–Dai languages. Related proposals include Austric (Wilhelm Schmidt in 1906) and Sino-Austronesian (Laurent Sagart in 1990, 2005). ...

 

العلاقات الآيسلندية التشيلية

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

Gard

Lambang Gard Gard ialah sebuah departemen yang terletak di Prancis Selatan di region Languedoc-Roussillon. Dinamai menurut sungai Gardon (atau Gard). Sejarah Daerah Gard dihuni oleh bangsa Romawi Kuno pada masa klasik. Dilalui oleh Via Domitia, yang dibangun pada 118 SM. Gard ialah salah satu dari 83 departemen yang diciptakan selama Revolusi Prancis pada 4 Maret 1790. Dibentuk dari bekas provinsi Languedoc. Geografi Gard ialah bagian dari region Languedoc Roussillon dan dikelilingi oleh depa...

 

1683 en France

Chronologie de la France ◄◄ 1679 1680 1681 1682 1683 1684 1685 1686 1687 ►► Chronologies Le château du Louvre en 1683. Alain Manesson Mallet, Description de l’Univers, t. 5, Paris, Denys Thierry, 1683.Données clés 1680 1681 1682  1683  1684 1685 1686Décennies :1650 1660 1670  1680  1690 1700 1710Siècles :XVe XVIe  XVIIe  XVIIIe XIXeMillénaires :-Ier Ier  IIe  IIIe Chronologies thématiques Art Architecture, Arts plastique...

 

Penyensoran

Halaman ini berisi artikel tentang pembatasan komunikasi dan informasi. Untuk pendeteksi sinyal, lihat Sensor.  Bagian dari seri tentangSensor Pada media Melarang buku-buku · Film yang dilarang Penyuntingan kembali film · Internet · Musik Pers · Radio · Berpikir Berbicara dan berekspresi Permainan video Metode Bunyi bip · Pembakaran buku Siaran tunda · Efek pedingin Konspirasi hening Perangkat lunak pengawasan is...

1994 United States Senate election in Vermont

1994 United States Senate election in Vermont ← 1988 November 8, 1994 2000 →   Nominee Jim Jeffords Jan Backus Gavin T. Mills Party Republican Democratic Independent Popular vote 106,505 85,868 12,465 Percentage 50.32% 40.57% 5.89% County results Municipality resultsJeffords:      30–40%      40–50%      50–60%      60–70%      7...

 

Heritage College & Seminary

Canadian evangelical institution in Ontario This article uses bare URLs, which are uninformative and vulnerable to link rot. Please consider converting them to full citations to ensure the article remains verifiable and maintains a consistent citation style. Several templates and tools are available to assist in formatting, such as reFill (documentation) and Citation bot (documentation). (August 2022) (Learn how and when to remove this template message) Heritage College & SeminaryCampus a...

 

African clawless otter

Species of carnivore 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: African clawless otter – news · newspapers · books · scholar · JSTOR (August 2010) (Learn how and when to remove this template message) African clawless otter On the banks of the Okavango River, Namibia Conservation status Near Threatened &...

Java Desktop System

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: Java Desktop System – news · newspapers · books · scholar · JSTOR (May 2023) (Learn how and when to remove this message) Java Desktop SystemSolaris 10 with Java Desktop System Release 3Developer(s)Oracle CorporationStable release3 Operating systemSolarisTypeDes...

 

John Deane (inventor)

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: John Deane inventor – news · newspapers · books · scholar · JSTOR (May 2022) (Learn how and when to remove this message) Deane Brothers diving helmet, replica Joint inventor of the diving helmet John Deane (1800–1884; known as The Infernal Diver), with h...

 

هنود

هنودمعلومات عامةنسبة التسمية الهند التعداد الكليالتعداد قرابة 1.21 مليار[1][2]تعداد الهند عام 2011ق. 1.32 مليار[3]تقديرات عام 2017ق. 30.8 مليون[4]مناطق الوجود المميزةبلد الأصل الهند البلد الهند  الهند نيبال 4,000,000[5] الولايات المتحدة 3,982,398[6] الإمار...

I'll Try Something New (song)

I'll Try Something NewSingle by The Miraclesfrom the album I'll Try Something New B-sideYou Never Miss a Good ThingReleasedApril 9, 1962RecordedHitsville USA (Studio A); 1961–1962GenreSoul, popLength3:00LabelTamlaT 54059Songwriter(s)Smokey RobinsonProducer(s)Smokey Robinson Berry GordyThe Miracles singles chronology What's So Good About Goodbye (1961) I'll Try Something New (1962) You've Really Got a Hold on Me (1962) AudioI'll Try Something New by The Miracles on YouTube I'll Try Something...

 

Portugal women's national under-20 basketball team

PortugalFIBA zoneFIBA EuropeNational federationPortuguese Basketball FederationU20 European ChampionshipAppearances8MedalsNoneU20 European Championship Division BAppearances9Medals Silver: 1 (2011) Bronze: 1 (2014) The Portugal women's national under-20 basketball team is a national basketball team of Portugal, administered by the Portuguese Basketball Federation.[1][2] It represents the country in women's international under-20 basketball competitions. FIBA U20 Women's Europ...

 

Kabinet Lee Hsien Loong II

Kabinet Lee Hsien Loong IIKabinet Pemerintahan Singapura ke-142006–2011Dibentuk30 Mei 2006Diselesaikan20 Mei 2011Struktur pemerintahanKepala negaraS. R. NathanKepala pemerintahanLee Hsien LoongPartai anggotaPartai Tindakan RakyatStatus di legislatifSupermayoritas 82 / 94 Partai oposisiPartai PekerjaPemimpin oposisiLow Thia KhiangSejarahPemilihan umumPemilihan umum Singapura 2006PeriodeParlemen Singapura ke-11PendahuluKabinet Lee Hsien Loong IPenggantiKabinet Lee Hsien Loong III Kabinet Lee ...

Pomona, California

City in California, United States City in California, United StatesPomona, CaliforniaCity Clockwise from top: Antiques Row, Abraham Lincoln Elementary School, California State Polytechnic University, Pomona, Lincoln Park Historic District FlagSealNickname: P-Town[citation needed]Motto: Vibrant – Safe – Beautiful[1]Location of Pomona in Los Angeles County and the U.S. state of CaliforniaPomonaLocation of Pomona, California in the United StatesShow map of...

 

Pergine Valsugana

Questa voce o sezione sull'argomento centri abitati del Trentino-Alto Adige non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Pergine Valsuganacomune Pergine Valsugana – VedutaPanorama di Pergine Valsugana ed il lago di Caldonazzo dalla frazione di Buss LocalizzazioneStato Italia Regione Trentino-Alto Adige Provincia Trento AmministrazioneSi...