Comparing the Expressibility of Languages Formed Using NP-Complete Operators

DOI10.1093/LOGCOM/1.3.305MaRDI QIDQ3358723zbMATH OpenOpenAlexFDO

Authors Iain Stewart

Publication date 1991

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/1.3.305

zbMATH Keywords

complexity classesfinite model theoryfirst-order languagesgraph colouringlogical expressibilityNP-completenessprojection translations

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Coloring of graphs and hypergraphs (05C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 139797
• scientific article; zbMATH DE number 88947
• Monotonicity and the Expressibility of NP Operators
• Computational complexity and the expressive power of logics
• Using the Hamiltonian path operator to capture NP

Cited in

(11)

• Circumscribing DATALOG: expressive power and complexity
• Context-sensitive transitive closure operators
• Some observations on holographic algorithms
• Normal forms for second-order logic over finite structures, and classification of NP optimization problems
• Generalized hex and logical characterizations of polynomial space
• scientific article; zbMATH DE number 139797 (Why is no real title available?)
• On completeness for NP via projection translations
• Relativized logspace and generalized quantifiers over finite ordered structures
• Capturing complexity classes with Lindström quantifiers
• Complete problems for monotone NP
• Methods for proving completeness via logical reductions

This page was built for publication: Comparing the Expressibility of Languages Formed Using NP-Complete Operators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3358723)