Descriptive Complexity for counting complexity classes

Simple item page
dc.contributor.authorArenas Saavedra, Marcelo Alejandro
dc.contributor.authorMuñoz Cruces, Martin Alonso
dc.contributor.authorRiveros Jaeger, Cristian
dc.date.accessioned2022-05-11T20:26:39Z
dc.date.available2022-05-11T20:26:39Z
dc.date.issued2017
dc.description.abstractDescriptive Complexity has been very successful in characterizing complexity classes of decision problems in terms of the properties definable in some logics. However, descriptive complexity for counting complexity classes, such as FP and #P, has not been systematically studied, and it is not as developed as its decision counterpart. In this paper, we propose a framework based on Weighted Logics to address this issue. Specifically, by focusing on the natural numbers we obtain a logic called Quantitative Second Order Logics (QSO), and show how some of its fragments can be used to capture fundamental counting complexity classes such as FP, #P and FPSPACE, among others. We also use QSO to define a hierarchy inside #P, identifying counting complexity classes with good closure and approximation properties, and which admit natural complete problems. Finally, we add recursion to QSO, and show how this extension naturally captures lower counting complexity classes such as #L.
dc.fuente.origenIEEE
dc.identifier.doi10.1109/LICS.2017.8005150
dc.identifier.eisbn978-1-5090-3018-7
dc.identifier.isbn9781509030194
dc.identifier.urihttps://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8005150
dc.identifier.urihttps://doi.org/10.1109/LICS.2017.8005150
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/63814
dc.information.autorucEscuela de ingeniería ; Arenas Saavedra, Marcelo Alejandro ; S/I ; 81488
dc.information.autorucEscuela de ingeniería ; Muñoz Cruces, Martin Alonso ; S/I ; 204015
dc.information.autorucEscuela de ingeniería ; Riveros Jaeger, Cristian ; S/I ; 131276
dc.language.isoen
dc.nota.accesoContenido parcial
dc.publisherIEEE
dc.relation.ispartofAnnual ACM/IEEE Symposium on Logic in Computer Science (LICS) (32° : 2017 : Reykjavik, Islandia)
dc.rightsacceso restringido
dc.subjectComplexity theory
dc.subjectSyntactics
dc.subjectRobustness
dc.subjectGrammar
dc.subjectElectronic mail
dc.subjectFocusing
dc.subjectSearch problems
dc.titleDescriptive Complexity for counting complexity classeses_ES
dc.typecomunicación de congreso
sipa.codpersvinculados81488
sipa.codpersvinculados204015
sipa.codpersvinculados131276
Files
Collections
Artículos de conferencia