Definition
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them.
Related concepts
AC0AC (complexity)Abiteboul–Vianu theoremAbstract machineCircuit complexityCo-NPComplexity classComputational complexity theoryComputational problemConcurrent random access machineConjunctive normal formDavid HarelDisjunctive normal formDomain of discourseELEMENTARYEXPTIMEFO (complexity)Fagin's theoremFinite model theoryFirst-order logicFixed-point logicFormal languageFunction (mathematics)HO (complexity)Higher-order logicHorn clauseInformation and ControlJournal of the ACMKrom formulaLH (complexity)L (complexity)Least fixed-point logicLeast fixed pointLogicLogical systemMoshe VardiNL (complexity)NP (complexity)NTIMENeil ImmermanOracle machinePH (complexity)PSPACEPTIMEP (complexity)Partial fixed-point logicPolynomial hierarchyQuery (complexity)Relation (mathematics)Ronald FaginSIAM Journal on ComputingSO (complexity)Second-order logicStar-free languageSubsetTetrationTheoretical Computer Science (journal)Time complexityTransitive closureTransitive closure logicTupleUniversal quantificationVictor Vianu
13 concepts already in your glossary