In this work, we study two simple yet general complexity classes, based on logspace Turing machines, which provide a unifying framework for efficient query evaluation in areas like information extraction and graph databases, among others. We investigate the complexity of three fundamental algorithmic problems for these classes: enumeration, counting and uniform generation of solutions, and show that they have several desirable properties in this respect. Both complexity classes are defined in terms of non-deterministic logspace transducers (NL transducers). For the first class, we consider the case of unambiguous NL transducers, and we prove constant delay enumeration, and both counting and uniform generation of solutions in polynomial time. For the second class, we consider unrestricted NL transducers, and we obtain polynomial delay enumeration, approximate counting in polynomial time, and polynomial-time randomized algorithms for uniform generation. More specifically, we show that each problem in this second class admits a fully polynomial-time randomized approximation scheme (FPRAS) and a polynomial-time Las Vegas algorithm for uniform generation. Interestingly, the key idea to prove these results is to show that the fundamental problem $\text{#NFA}$ admits an FPRAS, where $\text{#NFA}$ is the problem of counting the number of strings of length $n$ (given in unary) accepted by a non-deterministic finite automaton (NFA). While this problem is known to be $\text{#P}$-complete and, more precisely, $\text{SpanL}$-complete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem, and obtain as a welcome corollary that every function in $\text{SpanL}$ admits an FPRAS.


翻译:在这项工作中,我们研究了两个简单而一般的复杂类别,它们基于对数空间图灵机器, 提供了在信息提取和图形数据库等领域进行高效查询评估的统一框架。 我们调查了这些类别三个基本算法问题的复杂性: 查点、 计数和统一生成解决方案, 并表明它们在这方面具有若干可取的属性。 两个复杂类别的定义都是非确定性日志传输器( NL 传输器 ) 。 在头类中, 我们考虑的是清晰的 NL 转换器, 并且我们证明不断拖延查点, 以及混合时间计算和统一生成的解决方案的统一生成。 在第二类中, 我们考虑的是无限制 NL 转换器的计算和统一时间计算。 有趣的是, 大约在多元时间计数中, 混合时间随机的算法。 更具体地说, 我们发现, 第二类的每个问题都承认一个完全开放的美元- 开放的近值计划( FRA} 开始, 和 混合时间的拉斯维加斯计算方法, 美元 美元 。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
已删除
将门创投
3+阅读 · 2018年3月13日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年8月23日
Arxiv
0+阅读 · 2021年8月22日
Visual Distant Supervision for Scene Graph Generation
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
已删除
将门创投
3+阅读 · 2018年3月13日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员