Comparing the Expressibility of Languages Formed Using NP-Complete Operators

DOI10.1093/logcom/1.3.305zbMath0732.03032OpenAlexW2121714568MaRDI QIDQ3358723

Iain A. 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

NP-completenessgraph colouringfirst-order languagesfinite model theorycomplexity classeslogical expressibilityprojection translations

Mathematics Subject Classification ID

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

Related Items

Generalized hex and logical characterizations of polynomial space, On completeness for NP via projection translations, Normal forms for second-order logic over finite structures, and classification of NP optimization problems, Circumscribing DATALOG: expressive power and complexity, Capturing complexity classes with Lindström quantifiers, Relativized logspace and generalized quantifiers over finite ordered structures, Complete problems for monotone NP, Methods for proving completeness via logical reductions, Context-sensitive transitive closure operators