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

Abstract

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.

• The article: PDF (245,056 bytes)
• Source materials: ZIP (63,761 bytes)
• Original version (pre-July 2011): PDF (263,938 bytes)
• Self citation in BIBTeX (259 bytes)

DOI: 10.4086/cjtcs.2008.003

---

Volume 2008, Article 2
Volume 2008 Published articles


-------------->