×

Subclasses of binary NP. (English) Zbl 0901.68076

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.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03C13 Model theory of finite structures
03B15 Higher-order logic; type theory (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI Link