Polynomial-time maximisation classes: Syntactic hierarchy

Orestes Bueno, Prabhu Manyem

Research output: Contribution to conferencePaper

2 Scopus citations

Abstract

In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as P, NP, L and NL. However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper [13], we characterised the optimisation versions of P via expressions in second order logic, using universal Horn formulae with successor relations. In this paper, we study the syntactic hierarchy within the class of polynomially bound maximisation problems. We extend the result in the previous paper by showing that the class of polynomially-boundNP (not just P) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application - we show that the Bin Packing problem with online LIB constraints can be approximated to within a Θ (log n) bound, by providing a syntactic characterisation for this problem.
Original languageEnglish
Pages111-133
Number of pages23
StatePublished - 4 Aug 2008
Externally publishedYes
EventFundamenta Informaticae -
Duration: 4 Aug 2008 → …

Conference

ConferenceFundamenta Informaticae
Period4/08/08 → …

Keywords

  • Descriptive Complexity
  • Existential Second Order Logic
  • Finite Model Theory
  • Optimization
  • Quantifier Alternation
  • Quantifier Complexity
  • Syntactic Hierarchy

Fingerprint

Dive into the research topics of 'Polynomial-time maximisation classes: Syntactic hierarchy'. Together they form a unique fingerprint.

Cite this