Durand, Arnaud; Lautemann, Clemens; Schwentick, Thomas Subclasses of binary NP. (English) Zbl 0901.68076 J. Log. Comput. 8, No. 2, 189-207 (1998). Summary: Binary NP consists of all sets of finite structures which are expressible in existential second-order logic with second-order quantification restricted to relations of arity 2. We look at semantical restrictions of binary NP, where the second-order quantifiers range only over certain classes of relations. We consider mainly three types of classes of relations: unary functions, order relations and graphs with degree bounds. We show that many of these restrictions have the same expressive power and establish a four-level strict hierarchy, represented by sets, permutations, unary functions and arbitrary binary relations, respectively. Cited in 8 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 03C13 Model theory of finite structures 03B15 Higher-order logic; type theory (MSC2010) Keywords:descriptive complexity; existential second-order logic PDFBibTeX XMLCite \textit{A. Durand} et al., J. Log. Comput. 8, No. 2, 189--207 (1998; Zbl 0901.68076) Full Text: DOI Link