Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
From MaRDI portal
Publication:2868930
DOI10.1080/02331934.2011.625027zbMath1311.68073MaRDI QIDQ2868930
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
optimization; computational complexity; duality; decision problem; descriptive complexity; MaxHorn2SAT
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