Descriptive complexity for counting complexity classes

Descriptive complexity for counting complexity classes

000

Ciencias de la computación

Complejidad computacional.

Lógica computacional.

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

La complejidad descriptiva ha sido muy exitosa en caracterizar clases de complejidad de decisión en términos de propiedades definibles en algunas lógicas. Sin embargo, la complejidad descriptiva para clases de complejidad de conteo, como FP y #P, no ha sido estudiada sistemáticamente, y no está tan desarrollada como su análogo de decisión. En este artículo, proponemos un marco teórico basado en lógicas con peso para tratar este problema. Específicamente, al enfocarnos en los números naturales obtenemos una lógica llamada Lógica de Segundo Orden Cuantitativa (QSO), y mostramos cómo algunos de sus fragmentos pueden ser usados para capturar clases de complejidad de conteo fundamentales como FP, #P y FPSPACE, entre otras. También usamos QSO para definir una jerarquía dentro de #P, identificando clases de complejidad de conteo con buenas propiedades de clausura y aproximación, y que admiten problemas completos naturales. Finalmente, añadimos recursión a QSO, y mostramos cómo esta extensión captura naturalmente clases de complejidad de conteo inferiores como #L.

Muñoz Cruces, Martín Alonso,

2018-04-10T16:05:33Z

2018-04-10T16:05:33Z

2017

Arenas Saavedra, Marcelo Alejandro

Riveros Jaeger, Cristian

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

acceso abierto

xi, 70 hojas

application/pdf

es

tesis de maestría

10.7764/tesisUC/ING/21611

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

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