Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
From MaRDI portal
Publication:2868930
DOI10.1080/02331934.2011.625027zbMath1311.68073OpenAlexW1976048180MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)
Cites Work
- Unnamed Item
- 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