Details
| Original language | English |
|---|---|
| Title of host publication | 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 |
| Editors | Markus Blaser, Benjamin Monmege |
| Pages | 1-17 |
| Number of pages | 17 |
| ISBN (electronic) | 9783959771801 |
| Publication status | Published - 2021 |
| Event | 38th International Symposium on Theoretical Aspects of Computer Science - Saarbrücken, Germany Duration: 16 Mar 2021 → 19 Mar 2021 Conference number: 38 https://stacs2021.saarland-informatics-campus.de |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 187 |
| ISSN (Print) | 1868-8969 |
Abstract
Logarithmic space bounded complexity classes such as L and NL play a central role in space bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). They defined the operators paraW and paraβ for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[1] and paraβtail. Then, we consider counting versions of all four operators applied to logspace and obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0, 1)-matrices is #paraβtailL-hard and can be written as the difference of two functions in #paraβtailL. These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of #paraβtailL under parameterised logspace parsimonious reductions coincides with #paraβL, that is, modulo parameterised reductions, tailnondeterminism with read-once access is the same as read-once nondeterminism. Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Also, we show that the counting classes defined can naturally be characterised by parameterised variants of classes based on branching programs in analogy to the classical counting classes. Finally, we underline the significance of this topic by providing a promising outlook showing several open problems and options for further directions of research.
Keywords
- Counting Complexity, Logspace, Parameterized Complexity
ASJC Scopus subject areas
- Computer Science(all)
- Software
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. ed. / Markus Blaser; Benjamin Monmege. 2021. p. 1-17 40 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 187).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Parameterised Counting in Logspace
AU - Haak, Anselm
AU - Meier, Arne
AU - Prakash, Om
AU - Rao, B. V. Raghavendra
N1 - Conference code: 38
PY - 2021
Y1 - 2021
N2 - Logarithmic space bounded complexity classes such as L and NL play a central role in space bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). They defined the operators paraW and paraβ for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[1] and paraβtail. Then, we consider counting versions of all four operators applied to logspace and obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0, 1)-matrices is #paraβtailL-hard and can be written as the difference of two functions in #paraβtailL. These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of #paraβtailL under parameterised logspace parsimonious reductions coincides with #paraβL, that is, modulo parameterised reductions, tailnondeterminism with read-once access is the same as read-once nondeterminism. Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Also, we show that the counting classes defined can naturally be characterised by parameterised variants of classes based on branching programs in analogy to the classical counting classes. Finally, we underline the significance of this topic by providing a promising outlook showing several open problems and options for further directions of research.
AB - Logarithmic space bounded complexity classes such as L and NL play a central role in space bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). They defined the operators paraW and paraβ for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[1] and paraβtail. Then, we consider counting versions of all four operators applied to logspace and obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0, 1)-matrices is #paraβtailL-hard and can be written as the difference of two functions in #paraβtailL. These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of #paraβtailL under parameterised logspace parsimonious reductions coincides with #paraβL, that is, modulo parameterised reductions, tailnondeterminism with read-once access is the same as read-once nondeterminism. Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Also, we show that the counting classes defined can naturally be characterised by parameterised variants of classes based on branching programs in analogy to the classical counting classes. Finally, we underline the significance of this topic by providing a promising outlook showing several open problems and options for further directions of research.
KW - Counting Complexity
KW - Logspace
KW - Parameterized Complexity
UR - http://www.scopus.com/inward/record.url?scp=85115277252&partnerID=8YFLogxK
U2 - 10.48550/arXiv.1904.12156
DO - 10.48550/arXiv.1904.12156
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 17
BT - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021
A2 - Blaser, Markus
A2 - Monmege, Benjamin
T2 - 38th International Symposium on Theoretical Aspects of Computer Science
Y2 - 16 March 2021 through 19 March 2021
ER -