Publication details for Professor Iain StewartGate, J. & Stewart. I.A. (2010), Frameworks for logically classifying polynomial-time optimisation problems, in Ablayev F. & Mayr E.F. eds, Lecture Notes in Computer Science 6072: Proceedings of 5th International Computer Science Symposium in Russia. Kazan, Russia, Springer-Verlag, Berlin, 120-131.
- Publication type: Conference Paper
- ISSN/ISBN: 0302-9743, 1611-3349
- DOI: 10.1007/978-3-642-13182-0_12
- Keywords: descriptive complexity, optimisation problems, fixed-point logic
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We show that a logical framework, based around a fragment of existential second-order logic formerly proposed by others so as to capture the class of polynomially-bounded P-optimisation problems, cannot hope to do so, under the assumption that P ≠ NP. We do this by exhibiting polynomially-bounded maximisation and minimisation problems that can be expressed in the framework but whose decision versions are NP-complete. We propose an alternative logical framework, based around inflationary fixed-point logic, and show that we can capture the above classes of optimisation problems. We use the inductive depth of an inflationary fixed-point as a means to describe the objective functions of the instances of our optimisation problems.