Search engine for discovering works of Art, research articles, and books related to Art and Culture
ShareThis
Javascript must be enabled to continue!

Parameterised Counting in Logspace

View through CrossRef
AbstractLogarithmic space-bounded complexity classes such as$$\textbf{L} $$Land$$\textbf{NL} $$NLplay 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. They defined the operators$$\textbf{para}_{\textbf{W}}$$paraWand$$\textbf{para}_\beta $$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$$\textbf{para}_{\textbf{W}}$$paraWand$$\textbf{para}_\beta $$paraβby Stockhusen and Tantau, we introduce variants based on tail-nondeterminism,$$\textbf{para}_{{\textbf{W}}[1]}$$paraW[1]and$$\textbf{para}_{\beta {\textbf{tail}}}$$paraβtail. Then, we consider counting versions of all four operators and apply them to the class$$\textbf{L} $$L. We 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$$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$#paraβtailL-hard and can be written as the difference of two functions in$$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$#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$$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$#paraβtailLunder parameterised logspace parsimonious reductions coincides with$$\#\textbf{para}_\beta \textbf{L} $$#paraβL. In other words, in the setting of read-once access to nondeterministic bits, tail-nondeterminism coincides with unbounded nondeterminism modulo parameterised reductions. 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. Finally, we want to emphasise the significance of this topic by providing a promising outlook highlighting several open problems and directions for further research.
Title: Parameterised Counting in Logspace
Description:
AbstractLogarithmic space-bounded complexity classes such as$$\textbf{L} $$Land$$\textbf{NL} $$NLplay 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.
They defined the operators$$\textbf{para}_{\textbf{W}}$$paraWand$$\textbf{para}_\beta $$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$$\textbf{para}_{\textbf{W}}$$paraWand$$\textbf{para}_\beta $$paraβby Stockhusen and Tantau, we introduce variants based on tail-nondeterminism,$$\textbf{para}_{{\textbf{W}}[1]}$$paraW[1]and$$\textbf{para}_{\beta {\textbf{tail}}}$$paraβtail.
Then, we consider counting versions of all four operators and apply them to the class$$\textbf{L} $$L.
We 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$$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$#paraβtailL-hard and can be written as the difference of two functions in$$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$#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$$\#\textbf{para}_{\beta {\textbf{tail}}}\textbf{L} $$#paraβtailLunder parameterised logspace parsimonious reductions coincides with$$\#\textbf{para}_\beta \textbf{L} $$#paraβL.
In other words, in the setting of read-once access to nondeterministic bits, tail-nondeterminism coincides with unbounded nondeterminism modulo parameterised reductions.
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.
Finally, we want to emphasise the significance of this topic by providing a promising outlook highlighting several open problems and directions for further research.

Related Results

Instruction Supporting Children's Counting on for Addition and Counting up for Subtraction
Instruction Supporting Children's Counting on for Addition and Counting up for Subtraction
Children in the United States ordinarily invent a series of increasingly abbreviated and abstract strategies to solve addition and subtraction problems during their first 4 years i...
A Rapid Identification and Counting Method for Particle Sensing Using Machine Learning
A Rapid Identification and Counting Method for Particle Sensing Using Machine Learning
Cell identification and counting is important in all cell-related research steps including but not limited to culture, transformation, transfection, protein expression, etc. for ca...
Counting dense object of multiple types based on feature enhancement
Counting dense object of multiple types based on feature enhancement
IntroductionAccurately counting the number of dense objects in an image, such as pedestrians or vehicles, is a challenging and practical task. The existing density map regression m...
The impact of pill counting on resource-limited health facilities: a thematic qualitative analysis in eSwatini
The impact of pill counting on resource-limited health facilities: a thematic qualitative analysis in eSwatini
Abstract Research on health systems in resource-limited settings has garnered considerable attention, but the dispensing of individual prescriptions has not been tho...
IMPROVING EARLY CHILDHOOD COUNTING ABILITY THROUGH MODIFICATION OF ILLUSTRATED COUNTING BOOKS
IMPROVING EARLY CHILDHOOD COUNTING ABILITY THROUGH MODIFICATION OF ILLUSTRATED COUNTING BOOKS
Based on law no. 2 of 2003 concerning the national education system where early childhood education needs stimulation to assist physical and spiritual growth and development in ent...
A universal, damage-criterion-independent cycle counting method for multiaxial and variable amplitude fatigue
A universal, damage-criterion-independent cycle counting method for multiaxial and variable amplitude fatigue
None of the procedures for cycle-counting defined in the ASTM document with designation E1049-85 (Reapproved 2017) [1] are generally applicable to non-proportional, multi-axial Fat...
A Comprehensive Comparison Between Different Multiaxial Cycle Counting Procedure
A Comprehensive Comparison Between Different Multiaxial Cycle Counting Procedure
Abstract High-temperature nuclear design codes, such as Section III, Division 5 of the American ASME Boiler and Pressure Vessel Code and the French RCC-MRx, require ...

Back to Top