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 paraBeta 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 paraBeta by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[1] and paraBeta-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 #paraBeta-Tail-L-hard and can be written as the difference of two functions in #paraBetaTail-L. For example, we show that the closure of #paraBetaTail-L under parameterised logspace parsimonious reductions coincides with #paraBeta-L, that is, modulo parameterised reductions, tail-nondeterminism with read-once access is the same as read-once nondeterminism. 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 underline the significance of this topic by providing a promising outlook showing several open problems and options for further directions of research.
翻译:在此文件中, 我们引入了一个新的日志空间参数化计数框架 。 在 Elberfeld、 Stockhusen 和 Tantau 开发的参数化空间约束模型( PIP 2013, 2013, Algorithmica 2015 ) 的启发下, 我们引入了由 Elberfeld、 Stockhusen 和 Tantau 开发的参数化空间约束模型( PIP 2013, 2013, 2013, Algorithmica 2015 ) 。 它们定义了参数化空间复杂分类的操作员 parW 和 paraBeta 。 它们分别允许多读和读取访问, 使用这些操作员来测量图表中的自然问题。 使用这些操作员来测量图中自然问题的参数复杂性。 由 Stockhusen 和 TanteBeta 开发的参数约束模型, 以尾部的尾部定序值为新变数, 我们的定序- 读取- L- deal- deal- deal 和 缩略图中显示了两个LILL 的缩略图的变数。