We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Frameworks for logically classifying polynomial-time optimisation problems.

Gate, J. and Stewart, I. A. (2010) 'Frameworks for logically classifying polynomial-time optimisation problems.', in 5th International Computer Science Symposium in Russia, CSR 2010, 16-20 June 2010, Kazan, Russia ; proceedings. Berlin: Springer, pp. 120-131. Lecture notes in computer science. (6072).


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.

Item Type:Book chapter
Keywords:Descriptive complexity, Optimisation problems, Fixed-point logic.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:No date available
Date deposited:12 July 2010
Date of first online publication:June 2010
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar