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

DOI10.1080/02331934.2011.625027zbMath1311.68073MaRDI QIDQ2868930

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

optimization; computational complexity; duality; decision problem; descriptive complexity; MaxHorn2SAT

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q19: Descriptive complexity and finite models

Cites Work

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