Title: UNA PRESENTACION UNIFORME DE LA TEORIA DESCRIPTIVA DE LA COMPLEJIDAD COMPUTACIONAL
Abstract: The Theory of Descriptive Computational Complexity deals with Computational Complexity from the perspective of Logic. Among its main goals it is the logical characterization of computational complexity classes, traditionally defined in terms of resource bounded Turing machines. The presentation often found of this theory in the current literature, follows its historical development; hence, in consequence, for each particular computational complexity class one finds a particular translation of the associated computational model into the syntactic elements belonging to the logic intended for describing the complexity class. This long and ardous intelectual job can be simplified with a scheme that links a time or space complexity class with a formal language, which requires learning just a single translation of a particular Turing machine model (namely, the logarithmic space bounded deterministic Turing machine) into formulas of a particular logic (the extension of first order logic with the deterministic transitive closure operator). It is this uniform version of the Theory of Descriptive Computational Complexity which we present in this paper.
Publication Year: 2002
Publication Date: 2002-04-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot