Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR06-082 | 18th June 2006 00:00

Polynomial-Time Maximisation Classes: Syntactic Hierarchy


Authors: Prabhu Manyem
Publication: 11th July 2006 02:49
Downloads: 1230


In Descriptive Complexity, there is a vast amount of literature on
decision problems, and their classes such as \textbf{P, NP, L and NL}. ~
However, research on the descriptive complexity of optimisation problems
has been limited. In a previous paper [Man], we characterised
the optimisation versions of \textbf{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-bound \bf{NP} (not just
\bf{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 $\Theta(\log n)$ bound, by
providing a syntactic characterisation for this problem.

ISSN 1433-8092 | Imprint