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:||PDF - Accepted Version (186Kb)|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-13182-0_12|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-13182-0_12|
|Record Created:||01 Mar 2010 12:50|
|Last Modified:||31 Mar 2015 13:10|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|