Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap

DOI10.1080/02331934.2011.625027MaRDI QIDQ2868930zbMATH OpenOpenAlexFDO

Authors Prabhu Manyem

Publication date 19 December 2013

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331934.2011.625027

zbMATH Keywords

computational complexitydecision problemdescriptive complexitydualityMaxHorn2SAToptimization

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Syntactic characterizations of polynomial time optimization classes
• scientific article; zbMATH DE number 5499325
• scientific article; zbMATH DE number 515727
• Expressing combinatorial optimization problems by linear programs
• Logical definability of NP optimization problems

Cites work

• Approximation properties of NP minimization classes
• Capturing complexity classes by fragments of second-order logic
• Logical definability of NP optimization problems
• Nonlinear Programming
• On the complexity of the maximum satisfiability problem for Horn formulas
• Optimization, approximation, and complexity classes
• Quantifiers and approximation
• Syntactic characterizations of polynomial time optimization classes

This page was built for publication: Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap

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