Affiliations: Instituto de Matemática y Ciencias Afines
– IMCA, Calle Los Biólogos 245, Urb. San
César, Primera Etapa Lima 12, Lima, Perú.
E-mail: [email protected] | Centre for Informatics and Applied Optimisation, School
of IT and Mathematical Sciences, University of Ballarat Mount Helen, VIC 3350,
Australia. E-mail: [email protected]
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.
Keywords: Descriptive Complexity, FiniteModel Theory, Syntactic Hierarchy, Optimization, Quantifier Complexity, Quantifier Alternation, Existential Second Order Logic
