Normal forms for second-order logic over finite structures, and classification of NP optimization problems

DOI10.1016/0168-0072(95)00033-XzbMath0883.03015MaRDI QIDQ1919763

Thomas Eiter, Georg Gottlob, Yuri Gurevich

Publication date: 24 July 1996

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

minimization problemsnormal formmaximization problemsfinite successor structuresKolaitis-Thakur hierarchypolynomially bounded NP optimization problemssecond-order definability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13)

Related Items

Expressiveness of Logic Programs under the General Stable Model Semantics, Truth definitions in finite models, On the expressiveness of frame satisfiability and fragments of second-order logic, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, Abstraction for non-ground answer set programs, On the complexity of data disjunctions.

Uses Software

• Datalog

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 0-1 laws and decision problems for fragments of second-order logic
• Descriptive characterizations of computational complexity
• Optimization, approximation, and complexity classes
• Quantifiers and approximation
• Logical definability of NP optimization problems
• Model theory
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators