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 (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|
|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|