Frameworks for logically classifying polynomial-time optimisation problems

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

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