Home Online Resources Table of Contents

Journal of Logic and Computation, Volume 8, Issue 2: April 1998.

Subclasses of binary NP

A Durand1, C Lautemann2 and T Schwentick2

1Dept. d'Informatique, Universite de Caen, 14032 Caen cedex, France. E-mail: arnaud.durand@info.unicaen.fr, 2Institut fur Informatik, FB 17, Johannes Gutenberg-Universitat, D-55099 Mainz, Germany. E-mail: {cl,tick}@informatik.uni-mainz.de

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.

Keywords: Descriptive complexity, finite model theory, existential second-order logic.

Pages 189-207


This page is run by Oxford University Press, Great Clarendon Street, Oxford OX2 6DP, UK
as part of the OUP Journals World Wide Web service.
Comments and feedback: www-admin@oup.co.uk
URL: http://www.oup.co.uk/logcom/hdb/Volume_08/Issue_02/080189.sgm.abs.html
Last modification: 4 June 1998.
Copyright© Oxford University Press, 1998.