Efficient logspace classes for enumeration, counting and uniform generation

Efficient logspace classes for enumeration, counting and uniform generation

Logspace transducers

Constant delay enumeration

Approximate counting

Uniform generation

620

Ingeniería

Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2019

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 #NFA admits an FPRAS, where #NFA is the problem of counting the number of strings of length n accepted by a non-deterministic finite automaton (NFA). While this problem is known to be #P-complete and, more precisely, 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 SPANL admits an FPRAS.

Croquevielle Rendic, Luis Alberto

2022-10-07T20:10:07Z

2022-10-07T20:10:07Z

2019

Arenas Saavedra, Marcelo Alejandro

Pontificia Universidad Católica de Chile. Escuela de Ingeniería

acceso abierto

x, 77 páginas

application/pdf

en

tesis de maestría

10.7764/tesisUC/ING/65006

https://doi.org/10.7764/tesisUC/ING/65006

https://repositorio.uc.cl/handle/11534/65006