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} 开始, 和 混合时间的拉斯维加斯计算方法, 美元 美元 。