Chicago Journal of Theoretical Computer Science

Volume 2008

Article 3

Published by Dept. CS U. Chicago. Copyright 2008 CJTCS and the author.

Syntactic Characterizations of Polynomial Time Optimization Classes

Prabhu Manyem
School of Information Technology and Mathematical Sciences
University of Ballarat
Mount Helen, VIC 3350, Australia
May 22, 2008
(Submitted March 12, 2007)

The characterization of important complexity classes by logical descriptions has been an important and prolific area of Descriptive complexity. However, the central focus of the research has been the study of classes like P, NP, L and NL, corresponding to decision problems (e.g. the characterization of NP by Fagin [Fag74] and of P by Gradel [E. 91]). In contrast, optimization problems have received much less attention. Optimization problems corresponding to the NP class have been characterized in terms of logic expressions by Papadimitriou and Yannakakis, Panconesi and Ranjan, Kolaitis and Thakur, Khanna et al, and by Zimand. In this paper, we attempt to characterize the optimization versions of P via expressions in second order logic, many of them using universal Horn formulae with successor relations. These results nicely complement those of Kolaitis and Thakur [KT94] for polynomially bounded NP-optimization problems. The polynomially bounded versions of maximization and minimization problems are treated first, and then the maximization problems in the “not necessarily polynomially bounded” class.

DOI: 10.4086/cjtcs.2008.003
[] Volume 2008, Article 2
[back] Volume 2008 [back] Published articles
[CJCTS home]