Syntactic characterizations of polynomial time optimization classes

DOI10.4086/CJTCS.2008.003MaRDI QIDQ5414565zbMATH OpenOpenAlexFDO

Authors Prabhu Manyem

Publication date 6 May 2014

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4086/cjtcs.2008.003

zbMATH Keywords

descriptive complexityexistential second-order logicfinite model theoryoptimizationquantifier alternationquantifier complexitysyntactic hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 5499325
• Logical definability of NP optimization problems
• Descriptive characterizations of computational complexity
• scientific article; zbMATH DE number 515727
• Approximation properties of NP minimization classes

Cited in

(4)

• Normal forms for second-order logic over finite structures, and classification of NP optimization problems
• Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
• Frameworks for logically classifying polynomial-time optimisation problems
• scientific article; zbMATH DE number 5499325 (Why is no real title available?)

This page was built for publication: Syntactic characterizations of polynomial time optimization classes

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