Complete Problems Involving Boolean Labelled Structures and Projection Transactions

DOI10.1093/LOGCOM/1.6.861MaRDI QIDQ3988061zbMATH OpenOpenAlexFDO

Authors Iain 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

complexity classesfinite model theorypolynomial hierarchydescriptive complexity theorycomplete problemsprojection translationsreliability of networks of processors

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3927731
• scientific article; zbMATH DE number 408812
• On completeness for NP via projection translations
• On the structure of solution-graphs for Boolean formulas
• scientific article; zbMATH DE number 150219
• scientific article; zbMATH DE number 1670770
• Boolean satisfiability with transitivity constraints
• Complete problems for fixed-point logics
• On the structure of Boolean satisfiability
• scientific article; zbMATH DE number 871455

Cited in

(11)

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

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

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