Descriptive complexity of circuit-based counting classes

Downloadstatistik des Dokuments (Auswertung nach COUNTER):

Haak, Anselm: Descriptive complexity of circuit-based counting classes. Hannover : Gottfried Wilhelm Leibniz Universität, Diss., 2021, VIII, 175 S. DOI: https://doi.org/10.15488/11353

Zeitraum, für den die Download-Zahlen angezeigt werden:

Jahr: 
Monat: 

Summe der Downloads: 357




Kleine Vorschau
Zusammenfassung: 
In this thesis, we study the descriptive complexity of counting classes based on Boolean circuits.In descriptive complexity, the complexity of problems is studied in terms of logics required to describe them.The focus of research in this area is on identifying logics that can express exactly the problems in specific complexity classes.For example, problems are definable in ESO, existential second-order logic, if and only if they are in NP, the class of problems decidable in nondeterministic polynomial time.In the computation model of Boolean circuits, individual circuits have a fixed number of inputs.Circuit families are used to allow for an arbitrary number of input bits.A priori, the circuits in a family are not uniformly described, but one can impose this as an additional condition, e.g., requiring that there is an algorithm constructing them.For any circuit there is a function counting witnesses (or proofs) for the circuit producing the output 1.Consequently, any class of Boolean circuits has a corresponding class of counting functions.We characterize counting classes in terms of counting winning strategies in the model-checking game for different logics extending first-order logic, namely the classes #AC⁰, #NC¹, #SAC¹, and #AC¹.These classes restrict circuits to constant or logarithmic depth and in some cases also with respect to the fan-in of gates.In the case of the logarithmic-depth classes, this also requires new characterizations of the corresponding classes of Boolean circuit, as known results do not seem suitable for this approach. Our characterization of #AC⁰ also leads to a new characterization of the related class TC⁰.Our results apply both in the non-uniform as well as the uniform setting.We put our new characterization of #AC⁰ into perspective by studying connections to another logic-based counting class, #FO.This class is known to coincide with #P, the class of functions counting the number of accepting computation paths of NP-machines.We study a variant of #FO and the alternation hierarchy inside this class, as well as its connections to the class #AC⁰. Finally, we observe that often it is easier to characterize non-uniform circuit complexity classes than their uniform counterparts.This lends hope to the idea that characterizations of uniform classes could directly imply corresponding results in the non-uniform setting.We prove that this is true for a wide variety of classes, in particular for all classes we consider in this thesis.
Lizenzbestimmungen: CC BY-NC 3.0 DE
Publikationstyp: DoctoralThesis
Publikationsstatus: publishedVersion
Erstveröffentlichung: 2021
Die Publikation erscheint in Sammlung(en):Fakultät für Elektrotechnik und Informatik
Dissertationen

Verteilung der Downloads über den gewählten Zeitraum:

Herkunft der Downloads nach Ländern:

Pos. Land Downloads
Anzahl Proz.
1 image of flag of Germany Germany 205 57,42%
2 image of flag of United States United States 47 13,17%
3 image of flag of France France 18 5,04%
4 image of flag of China China 18 5,04%
5 image of flag of No geo information available No geo information available 12 3,36%
6 image of flag of Czech Republic Czech Republic 8 2,24%
7 image of flag of Russian Federation Russian Federation 6 1,68%
8 image of flag of Iran, Islamic Republic of Iran, Islamic Republic of 6 1,68%
9 image of flag of India India 5 1,40%
10 image of flag of Poland Poland 4 1,12%
    andere 28 7,84%

Weitere Download-Zahlen und Ranglisten:


Hinweis

Zur Erhebung der Downloadstatistiken kommen entsprechend dem „COUNTER Code of Practice for e-Resources“ international anerkannte Regeln und Normen zur Anwendung. COUNTER ist eine internationale Non-Profit-Organisation, in der Bibliotheksverbände, Datenbankanbieter und Verlage gemeinsam an Standards zur Erhebung, Speicherung und Verarbeitung von Nutzungsdaten elektronischer Ressourcen arbeiten, welche so Objektivität und Vergleichbarkeit gewährleisten sollen. Es werden hierbei ausschließlich Zugriffe auf die entsprechenden Volltexte ausgewertet, keine Aufrufe der Website an sich.