Complete Problems Involving Boolean Labelled Structures and Projection Transactions

DOI10.1093/logcom/1.6.861zbMath0744.03040OpenAlexW2065546707MaRDI QIDQ3988061

Iain A. Stewart

Publication date: 28 June 1992

Published in: Journal of Logic and Computation (Search for Journal in Brave)

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

zbMATH Keywords

polynomial hierarchyfinite model theorycomplexity classesdescriptive complexity theorycomplete problemsprojection translationsreliability of networks of processors

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (10)

Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy. ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ Enhancing context knowledge repositories with justifiable exceptions ⋮ Methods for proving completeness via logical reductions ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Normal Form Nested Programs ⋮ Positive versions of polynomial time ⋮ Succinctness as a source of complexity in logical formalisms ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Context-sensitive transitive closure operators

This page was built for publication: Complete Problems Involving Boolean Labelled Structures and Projection Transactions