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 的缩略图的变数。

0
下载
关闭预览

相关内容

Algorithmica是一本国际性的期刊,它出版关于解决实际领域中出现的问题的算法的理论论文,以及对实际重要性或技术具有普遍吸引力的实验论文。算法的发展是计算机科学的一个组成部分。计算机应用的日益复杂和范围使得高效算法的设计必不可少。此外,该杂志还设有两个专区:应用经验、将理论成果应用到实际情况中的发现和问题、提供有关计算机科学选定主题的问题的短文。官网链接:https://link.springer.com/journal/453
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
7+阅读 · 2018年10月12日
Arxiv
0+阅读 · 2021年3月9日
Arxiv
3+阅读 · 2018年8月17日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
7+阅读 · 2018年10月12日
Top
微信扫码咨询专知VIP会员