Logical definability of NP optimization problems
From MaRDI portal
Publication:1342522
DOI10.1006/inco.1994.1100zbMath0820.68048MaRDI QIDQ1342522
Phokion G. Kolaitis, Madhukar N. Thakur
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
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
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, A note on the approximation of the MAX CLIQUE problem, Integer programming as a framework for optimization and approximability, The complexity and approximability of finding maximum feasible subsystems of linear relations, The approximability of non-Boolean satisfiability problems and restricted integer programming, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Normal forms for second-order logic over finite structures, and classification of NP optimization problems, Max NP-completeness made easy, Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Polynomial approximation: a structural and operational study. (Abstract of thesis), Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap
