Generalized Quantifiers and Logical Reducibilities

Citations Over TimeTop 10% of 1995 papers

Abstract

We consider the problem of defining a logic that captures exactly the polynomial time computable properties of finite structures, by extending first-order logic (FO) and fixed-point logic (FP) by means of Lindstrom quantifiers. In particular,we define infinite uniform sequences of quantifiers and show that these correspond to a natural notion of logical reducibility. We show that if there is any logic that captures the complexity class PTTME, in the sense of a recursive enumeration of PTIME properties, then there is one that is an extension of FO by a uniform sequence of quantifiers. This is established through a general result linking the existence of complete problems for a complexity class to the existence of recursive index sets for the class, for a wide variety of complexity classes.

Related Papers

• → Capturing Relativized Complexity Classes without Order(1998)12 cited
• → Characterization of Complexity Classes in Higher-Order Logic(1987)15 cited
• → Choiceless Logarithmic Space(2019)2 cited
• → The structure of graphs and new logics for the characterization of Polynomial Time(2011)28 cited
• → Randomisation and Derandomisation in Descriptive Complexity Theory(2011)