Cookies

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).

Abstract

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 (Copyright agreement prohibits open access to the full-text) - Accepted Version
Publisher-imposed embargo
(186Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/978-3-642-13182-0_12
Publisher statement:
Record Created:01 Mar 2010 12:50
Last Modified:09 Oct 2014 13:40

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library