Descriptive complexity for counting complexity classes

Simple item page
dc.contributor.advisorArenas Saavedra, Marcelo Alejandro
dc.contributor.advisorRiveros Jaeger, Cristian
dc.contributor.authorMuñoz Cruces, Martín Alonso,
dc.contributor.otherPontificia Universidad Católica de Chile. Escuela de Ingeniería
dc.date.accessioned2018-04-10T16:05:33Z
dc.date.available2018-04-10T16:05:33Z
dc.date.issued2017
dc.descriptionTesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2017
dc.description.abstractLa 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.
dc.format.extentxi, 70 hojas
dc.identifier.doi10.7764/tesisUC/ING/21611
dc.identifier.urihttps://doi.org/10.7764/tesisUC/ING/21611
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/21611
dc.language.isoes
dc.nota.accesoContenido completo
dc.rightsacceso abierto
dc.subject.ddc000
dc.subject.deweyCiencias de la computaciónes_ES
dc.subject.otherComplejidad computacional.es_ES
dc.subject.otherLógica computacional.es_ES
dc.titleDescriptive complexity for counting complexity classeses_ES
dc.typetesis de maestría
sipa.codpersvinculados81488
sipa.codpersvinculados131276
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Muñoz_Martín.pdf
Size:
654.13 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.31 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
3.01 Tesis magíster