Frameworks for logically classifying polynomial-time optimisation problems

Gate, J.; Stewart., I.A.

doi:10.1007/978-3-642-13182-0_12

Frameworks for logically classifying polynomial-time optimisation problems

Gate, J.; Stewart., I.A.

Authors

J. Gate

Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor

Contributors

F. Ablayev
Editor

E. F. Mayr
Editor

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.

Citation

Gate, J., & Stewart., I. (2010). Frameworks for logically classifying polynomial-time optimisation problems. In F. Ablayev, & E. F. Mayr (Eds.), 5th International Computer Science Symposium in Russia, CSR 2010, 16-20 June 2010, Kazan, Russia ; proceedings (120-131). https://doi.org/10.1007/978-3-642-13182-0_12

Conference Name	5th International Computer Science Symposium in Russia (CSR 2010)
Conference Location	Kazan, Russia
Start Date	Jun 16, 2010
End Date	Jun 20, 2010
Publication Date	Jun 20, 2010
Deposit Date	Mar 1, 2010
Publicly Available Date	Jul 12, 2010
Pages	120-131
Series Title	Lecture notes in computer science
Series Number	6072
Series ISSN	0302-9743,1611-3349
Book Title	5th International Computer Science Symposium in Russia, CSR 2010, 16-20 June 2010, Kazan, Russia ; proceedings.
ISBN	9783642131813
DOI	https://doi.org/10.1007/978-3-642-13182-0_12
Keywords	Descriptive complexity, Optimisation problems, Fixed-point logic.
Public URL	https://durham-repository.worktribe.com/output/1160132
Publisher URL	http://www.dur.ac.uk/i.a.stewart/Papers/OptFrameworks.pdf