ACC0

Sketch of an ACC-circuit: For a fixed number m, the circuit consists of NOT-, AND-, OR-, and (Mod m)-Gates. The fan-in of each gate is bounded by a polynomial and the depth of the circuit is bounded by a constant.

ACC0, sometimes called ACC, is a class of computational models and problems defined in circuit complexity, a field of theoretical computer science. The class is defined by augmenting the class AC0 of constant-depth "alternating circuits" with the ability to count; the acronym ACC stands for "AC with counters".[1] Specifically, a problem belongs to ACC0 if it can be solved by polynomial-size, constant-depth circuits of unbounded fan-in gates, including gates that count modulo a fixed integer. ACC0 corresponds to computation in any solvable monoid. The class is very well studied in theoretical computer science because of the algebraic connections and because it is one of the largest concrete computational models for which computational impossibility results, so-called circuit lower bounds, can be proved.

Definitions

Informally, ACC0 models the class of computations realised by Boolean circuits of constant depth and polynomial size, where the circuit gates includes "modular counting gates" that compute the number of true inputs modulo some fixed constant.

More formally, a language belongs to AC0[m] if it can be computed by a family of circuits C1, C2, ..., where Cn takes n inputs, the depth of every circuit is constant, the size of Cn is a polynomial function of n, and the circuit uses the following gates: AND gates and OR gates of unbounded fan-in, computing the conjunction and disjunction of their inputs; NOT gates computing the negation of their single input; and unbounded fan-in MOD-m gates, which compute 1 if the number of input 1s is a multiple of m. A language belongs to ACC0 if it belongs to AC0[m] for some m.

In some texts, ACCi refers to a hierarchy of circuit classes with ACC0 at its lowest level, where the circuits in ACCi have depth O(login) and polynomial size.[1]

The class ACC0 can also be defined in terms of computations of nonuniform deterministic finite automata (NUDFA) over monoids. In this framework, the input is interpreted as elements from a fixed monoid, and the input is accepted if the product of the input elements belongs to a given list of monoid elements. The class ACC0 is the family of languages accepted by a NUDFA over some monoid that does not contain an unsolvable group as a subsemigroup.[2]

Computational power

The class ACC0 includes AC0. This inclusion is strict, because a single MOD-2 gate computes the parity function, which is known to be impossible to compute in AC0. More generally, the function MODm cannot be computed in AC0[p] for prime p unless m is a power of p.[3]

The class ACC0 is included in TC0. It is conjectured that ACC0 is unable to compute the majority function of its inputs (i.e. the inclusion in TC0 is strict), but this remains unresolved as of July 2018.

Every problem in ACC0 can be solved by circuits of depth 2, with AND gates of polylogarithmic fan-in at the inputs, connected to a single gate computing some symmetric (not depending on the order of the inputs) function.[4] These circuits are called SYM+-circuits. The proof follows ideas of the proof of Toda's theorem.

Williams (2011) proves that ACC0 does not contain NEXPTIME. The proof uses many results in complexity theory, including the time hierarchy theorem, IP = PSPACE, derandomization, and the representation of ACC0 via SYM+ circuits.[5] Murray & Williams (2018) improves this bound and proves that ACC0 does not contain NQP (nondeterministic quasipolynomial time).

It is known that computing the permanent is impossible for LOGTIME-uniform ACC0 circuits, which implies that the complexity class PP is not contained in LOGTIME-uniform ACC0.[6]

Notes

References

  • Allender, Eric (1996), "Circuit complexity before the dawn of the new millennium", 16th Conference on Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India, December 18–20, 1996, Lecture Notes in Computer Science, vol. 1180, Springer, pp. 1–18, doi:10.1007/3-540-62034-6_33
  • Allender, Eric; Gore, Vivec (1994), "A uniform circuit lower bound for the permanent" (PDF), SIAM Journal on Computing, 23 (5): 1026–1049, doi:10.1137/S0097539792233907, archived from the original (PDF) on 2016-03-03, retrieved 2012-07-02
  • Barrington, D.A. (1989), "Bounded-width polynomial-size branching programs recognize exactly those languages in NC1" (PDF), Journal of Computer and System Sciences, 38 (1): 150–164, doi:10.1016/0022-0000(89)90037-8.
  • Barrington, David A. Mix (1992), "Some problems involving Razborov-Smolensky polynomials", in Paterson, M.S. (ed.), Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990., London Mathematical Society Lecture Notes Series, vol. 169, pp. 109–128, ISBN 0-521-40826-1, Zbl 0769.68041.
  • Barrington, D.A.; Thérien, D. (1988), "Finite monoids and the fine structure of NC1", Journal of the ACM, 35 (4): 941–952, doi:10.1145/48014.63138, S2CID 52148641
  • Beigel, Richard; Tarui, Jun (1994), "On ACC", Computational Complexity, 4 (4): 350–366, doi:10.1007/BF01263423, S2CID 2582220.
  • Clote, Peter; Kranakis, Evangelos (2002), Boolean functions and computation models, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, ISBN 3-540-59436-1, Zbl 1016.94046
  • Razborov, A. A. (1987), "Lower bounds for the size of circuits of bounded depth with basis {⊕,∨}", Math. Notes of the Academy of Science of the USSR, 41 (4): 333–338.
  • Smolensky, R. (1987), "Algebraic methods in the theory of lower bounds for Boolean circuit complexity", Proc. 19th ACM Symposium on Theory of Computing, pp. 77–82, doi:10.1145/28395.28404.
  • Murray, Cody D.; Williams, Ryan (2018), "Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP", Proc. 50th ACM Symposium on Theory of Computing, pp. 890–901, doi:10.1145/3188745.3188910, hdl:1721.1/130542, S2CID 3685013
  • Thérien, D. (1981), "Classification of finite monoids: The language approach", Theoretical Computer Science, 14 (2): 195–208, doi:10.1016/0304-3975(81)90057-8.
  • Vollmer, Heribert (1999), Introduction to Circuit Complexity, Berlin: Springer, ISBN 3-540-64310-9.
  • Williams, Ryan (2011), "Non-uniform ACC Circuit Lower Bounds", 2011 IEEE 26th Annual Conference on Computational Complexity (PDF), pp. 115–125, doi:10.1109/CCC.2011.36, ISBN 978-1-4577-0179-5.

Read other articles:

بو ويلش معلومات شخصية الميلاد 30 نوفمبر 1951 (72 سنة)  ياردلي (بنسيلفانيا)  الإقامة لوس أنجلوس  مواطنة الولايات المتحدة  الزوجة كاثرين أوهارا (1992–)  الحياة العملية المدرسة الأم جامعة أريزونا  المهنة مخرج أفلام،  وكاتب سيناريو  اللغات الإنجليزية  المواقع IM...

 

Andreas Lange Andreas Lange (* 1964 in Höxter) ist ein deutscher evangelisch-lutherischer Theologe. Seit 1992 ist er Pfarrer in der Kirchengemeinde St. Nicolai in Lemgo und seit 2005 Lutherischer Superintendent der Lippischen Landeskirche. Lange ist Vizepräses der EKD-Synode. Inhaltsverzeichnis 1 Leben und Werdegang 2 Funktionen 3 Auszeichnungen 4 Schriften 5 Einzelnachweise Leben und Werdegang Andreas Lange stammt aus Detmold. Nach dem Abitur 1984 am Gymnasium Leopoldinum studierte er in B...

 

此條目翻譯品質不佳。 (2023年3月3日)翻譯者可能不熟悉中文或原文語言,也可能使用了機器翻譯。請協助翻譯本條目或重新編寫,并注意避免翻译腔的问题。明顯拙劣的翻譯請改掛{{d|G13}}提交刪除。 赛义德·胡尔希德·艾哈迈德·沙阿巴基斯坦反對黨領袖任期2013年6月7日—2018年5月31日总统阿西夫·阿里·扎爾達里 馬姆努恩·侯賽因总理納瓦茲·謝里夫前任尼萨尔·阿里·汗继...

Museum to honor bluegrass music International Bluegrass Music Hall of FameTypeMusic AssociationGenreBluegrassFounded1991Headquarters311 W 2nd St, Owensboro, KY 42301 Owensboro, Kentucky, United StatesWebsitehttps://www.bluegrasshall.org/ Induction to the International Bluegrass Music Hall of Fame, called the International Bluegrass Music Hall of Honor from its creation in 1991 through 2006, is managed by the International Bluegrass Music Association, and the Hall itself is maintained at the B...

 

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها. هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (ديسمبر 2019) بدأ تاريخ النقل البري بالوسائل البدائية التي تعتمد على ا...

 

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: Pemanggang vakum – berita · surat kabar · buku · cendekiawan · JSTOR Pemanggang vakum merupakan mesin penggorengan dengan sistem vakum untuk membuat aneka jenis keripik buah dan sayur dengan sistem vakum...

تحوي هذه المقالة أو هذا القسم ترجمة آلية. فضلًا، ساهم في تدقيقها وتحسينها أو إزالتها لأنها تخالف سياسات ويكيبيديا. (نقاش) إكوادوري لبنانيأعلام لبنانيون:عبد الله بوكرم، جميل ماهود، جايمي نبوت، فاليسكا صعبالتعداد الكليالتعداد تقديرات مختلفةمناطق الوجود المميزة غواياكيل و...

 

Lee Da-witLahir3 Maret 1994 (umur 29)Nama lainLee DavidPekerjaanAktor Lee David (bahasa Korea: 이다윗) (lahir 3 Maret 1994) adalah aktor asal Korea Selatan.[1] Filmografi Serial televisi Tahun Judul Peran Jaringan 2001 TV Novel: Flower Story KBS1 2003 Age of Warriors Choe Woo KBS1 The King's Woman Pangeran Sunhwa SBS 2006 Yeon Gaesomun young Kim Yushin SBS 2007 Bad Woman, Good Woman MBC Yi San Pangeran Euneon MBC 2008 Iljimae Cha-dol/Shi-hoo muda SBS My Pitiful Sister...

 

Former president of Intel. Currently CEO of Ampere Computing Renée JamesBornLos Angeles County, CaliforniaNationalityAmericanAlma materUniversity of Oregon (B.A. and M.B.A)Occupation(s)Founder, Chairman and CEO at Ampere Computing; Operating Executive at The Carlyle Group Renée J. James (born June 25, 1964) is an American technology executive, who was formerly the president of Intel. She founded Ampere Computing in October 2017, is currently its Chairman and CEO.[1] She is also...

Private day school in Liverpool, EnglandSt Mary's CollegeAddressEverest RoadCrosbyLiverpool, L23 5TWEnglandCoordinates53°29′18″N 3°01′27″W / 53.488335°N 3.024051°W / 53.488335; -3.024051InformationTypePrivate day schoolMottoFidem vita fateri(Latin: Show your faith by the way you live)Religious affiliation(s)Roman CatholicEstablished1919Local authoritySeftonChairman of GovernorsMr C J CleughPrincipalMr M KennedyGenderCoeducationalAge2 to 18Enrolment766 (...

 

Overview of England at the Cricket World Cup The England cricket team have appeared in every edition of the Cricket World Cup to date, being crowned champions in 2019.[1] In addition, they were losing finalists in 1979, 1987 and 1992.[2] England have been eliminated from the tournament in the group stage on five occasions (1999, 2003, 2007, 2015 and 2023) England were the inaugural hosts of the World Cup, in 1975. The country has since hosted the tournament a further four time...

 

 Główny artykuł: Mistrzostwa Europy w Lekkoatletyce 1958. Mistrzostwa Europy w Lekkoatletyce 1958Bieg na 200 metrów mężczyzn Manfred Germar David Segal Jocelyn Delecour Manfred Germar Jocelyn Delecour Bieg na dystansie 200 metrów mężczyzn był jedną z konkurencji rozgrywanych podczas VI Mistrzostw Europy w Sztokholmie. Biegi eliminacyjne i półfinałowe zostały rozegrane 22 sierpnia, a bieg finałowy 23 sierpnia 1958 roku. Zwycięzcą tej konkurencji został reprezentant wsp...

M.E VoicesInformasi latar belakangNama lainM.E eMbung ElehAsalBandung, IndonesiaGenreR&BSoulTahun aktif1991–1999 2009–SekarangLabelAriolaCeepee ProductionOrlando StudioCityParty DigitalArtis terkaitDenny Didan 9 Seasons SabaAnggotaDenny Saba Fery Martawidjaja Widi Cipto Utomo Didan FitrasaktiMantan anggotaIrvan Natadiningrat M.E Voices atau yang ia dikenal dengan M.E dan eMbung Eleh merupakan grup vokal pria asal Indonesia yang dibentuk pada tahun 1991 ini berawal terdiri dari Didan F...

 

2022 soundtrack albums Bullet Train (Original Motion Picture Soundtrack)Soundtrack album by Various artistsReleasedAugust 3, 2022GenrePopjazzrockEDMheavy metalLength45:59LabelArista Records Bullet Train (Original Motion Picture Score)Film score by Dominic LewisReleasedAugust 5, 2022GenreFilm scoreLength56:17LabelMilan RecordsProducerDominic LewisDominic Lewis chronology The King's Man(2021) Bullet Train(2022) Bullet Train (Original Motion Picture Soundtrack) is the soundtrack album to...

 

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: Amal International School – news · newspapers · books · scholar · JSTOR (June 2022) (Learn how and when to remove this template message) Private school in Colombo, Sri LankaAmal International SchoolLocationWellawattaColomboSri LankaCoordinates06°53′03″N 79...

Deze kerk is te onderscheiden van de gelijknamige parochiekerk Sint-Willibrordus in Berchem. Sint-Willibrorduskerk Plaats Antwerpen-Noord Gewijd aan Sint-Willibrordus Coördinaten 51° 13′ NB, 4° 26′ OL Gebouwd in 1891 Architectuur Architect(en) • Leonard Blomme,• Henri Blomme Bouwmateriaal Baksteen Toren 84 m Koor met koorommegang Schip Middenbeuk en twee zijbeuken Interieur Preekstoel • Ontwerper: K. Toen.• Beeldhouwer: Jean-Baptist Van Wint (1901-1902) Altaar...

 

American politician Thaddeus J. DulskiChairman of the U.S. House Post Office and Civil Service CommitteeIn office1967–1974Preceded byTom J. MurraySucceeded byWilliam D. FordMember of theU.S. House of Representativesfrom New YorkIn officeJanuary 3, 1959 – December 31, 1974Preceded byEdmund P. RadwanSucceeded byHenry J. NowakConstituency41st district (1959–73)37th district (1973–74) Personal detailsBorn(1915-09-27)September 27, 1915Buffalo, New YorkDiedOctober 11, 1988(1988-10-...

 

Scotch Bonnet Ridge is a geologic ridge that crosses the Canada-United States border, in Lake Ontario, south of Prince Edward County.[1] Scotch Bonnet Island and Nicholson Island lie off the shore of Prince Edward County. The ridge is composed of glacio-lacustrine clay and till.[2] References ^ Marc Seguin (2015). For Want of a Lighthouse: Building the Lighthouses of Eastern Lake Ontario 1828–1914. Trafford Publishing. ISBN 9781490756714. Retrieved 2017-06-22. ^ Scotch ...

In this Chinese name, the family name is Wu (surname 武). Wu Yuxiang武禹襄Drawing of Wu YuxiangBorn1812?Died1880?StyleWu (Hao)-style tai chiNotable studentsLi Yiyu (李亦畬)Li Qixuan Wu YuxiangChinese武禹襄TranscriptionsStandard MandarinHanyu PinyinWǔ YǔxiāngWade–GilesWu Yu-hsiang Part of a series onChinese martial arts (Wushu) Styles of Chinese martial arts List of Chinese martial arts Terms Chin Na Fa jin Kung fu Neigong Neijia Qi Qigong Shifu Yin and yang Historical locations...

 

Etsu Nupe of Bida Yahya AbubakarEtsu Nupe (Etsu Nupe means King of Nupe)Etsu Nupe (King of Nupe) Reign2003Coronation20 August 2003PredecessorUmaru Sanda NdayakoBornYahaya Abubakar (1952-09-12) 12 September 1952 (age 71)BidaSpouseMarried to Four WivesNamesYahaya Abubakar Sanganuwar NakordiRoyalUsman Zaki Ruling houseFatherAlh. Abubakar Saganuwa (Nakordi Nupe)MotherHaj. Habiba Bantigi NdayakoReligionIslamOccupationEx-Military, Traditional Ruler Yahaya Abubakar CFR is a traditional ruler (E...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!