Two logical hierarchies of optimization problems over the real numbers

DOI10.1002/MALQ.200510021MaRDI QIDQ3376539zbMATH OpenOpenAlexFDO

Authors Uffe Flarup, Klaus Meer

Publication date 24 March 2006

Published in MLQ (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200510021

zbMATH Keywords

real number modelslogical description of optimization problemsmeta-finite model theory

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Mathematical Foundations of Computer Science 2005
• Approximation Classes for Real Number Optimization Problems
• Logical definability of NP optimization problems
• Continuous optimization problems and a polynomial hierarchy of real functions
• Quantifiers and approximation

Cites work

• scientific article; zbMATH DE number 1086675 (Why is no real title available?)
• Algorithms in real algebraic geometry
• Counting complexity classes for numeric computations II
• Mathematical Foundations of Computer Science 2005
• New Computational Paradigms

Cited in

(4)

• Normal forms for second-order logic over finite structures, and classification of NP optimization problems
• Mathematical Foundations of Computer Science 2005
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals

This page was built for publication: Two logical hierarchies of optimization problems over the real numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3376539)