Logical definability of NP optimization problems

DOI10.1006/inco.1994.1100zbMath0820.68048OpenAlexW2063981365MaRDI QIDQ1342522

Madhukar N. Thakur, Phokion G. Kolaitis

Publication date: 11 January 1995

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/1f5ea005839073adcd272569a8f78cc13ba46169

zbMATH Keywords

NP optimization problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Unnamed Item ⋮ Polynomial approximation: a structural and operational study. (Abstract of thesis) ⋮ The complexity and approximability of finding maximum feasible subsystems of linear relations ⋮ Normal forms for second-order logic over finite structures, and classification of NP optimization problems ⋮ On the approximability of the maximum common subgraph problem ⋮ Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Approximating minimum keys and optimal substructure screens ⋮ Max NP-completeness made easy ⋮ A survey on the structure of approximation classes ⋮ Polynomially bounded minimization problems which are hard to approximate ⋮ A note on the approximation of the MAX CLIQUE problem ⋮ Approximate solution of NP optimization problems ⋮ On input read-modes of alternating Turing machines ⋮ A note on the descriptive complexity of maximization problems ⋮ Structure of polynomial-time approximation ⋮ The approximability of non-Boolean satisfiability problems and restricted integer programming ⋮ Integer programming as a framework for optimization and approximability ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. ⋮ Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap