Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/9306

Syntactic approximations to computational complexity classes
Arratia Quesada, Argimiro Alejandro; Ortiz Gómez, Carlos
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge
We present a formal syntax of approximate formulas suited for the logic with counting quantifiers SOLP. This logic was studied by us in [1] where, among other properties, we showed: (i) In the presence of a built–in (linear) order, SOLP can describe NP–complete problems and fragments of it capture classes like P and NL; (ii) weakening the ordering relation to an almost order we can separate meaningful fragments, using a combinatorial tool adapted to these languages. The purpose of the approximate formulas presented here, is to provide a syntactic approximation to logics contained in SOLP with built-in order, that should be complementary of the semantic approximation based on almost orders, by producing approximating logics where problems are described within a small counting error. We state and prove a Bridge Theorem that links expressibility in fragments of SOLP over almostordered structures to expressibility with respect to approximate formulas for the corresponding fragments over ordered structures. A consequence of these results is that proving inexpressibility results over fragments of SOLP with built-in order could be done by proving inexpressibility over the corresponding fragments with built-in almost order, where separation proofs are allegedly easier.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Computer logic
Computational complexity
Lògica informàtica
Complexitat computacional
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.