Methods for proving completeness via logical reductions

DOI10.1016/0304-3975(93)90109-7MaRDI QIDQ685391zbMATH OpenOpenAlexFDO

Authors Iain Stewart

Publication date 20 December 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90109-7

zbMATH Keywords

descriptive complexity theorycomplete problems

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

• On completeness for NP via projection translations
• Succinct representation, leaf languages, and projection reductions
• scientific article; zbMATH DE number 408812
• The completeness problem for modal logic
• Logics for complexity classes

Cites work

• scientific article; zbMATH DE number 1678393 (Why is no real title available?)
• scientific article; zbMATH DE number 3889514 (Why is no real title available?)
• scientific article; zbMATH DE number 4106276 (Why is no real title available?)
• scientific article; zbMATH DE number 88947 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 408812 (Why is no real title available?)
• scientific article; zbMATH DE number 219246 (Why is no real title available?)
• A complexity theory based on Boolean algebra
• A taxonomy of problems with fast parallel algorithms
• Bounded Query Classes
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Complete Problems Involving Boolean Labelled Structures and Projection Transactions
• Complete problems for symmetric logspace involving free groups
• Constant Depth Reducibility
• Languages that Capture Complexity Classes
• Maze recognizing automata and nondeterministic tape complexity
• Nondeterministic Space is Closed under Complementation
• On uniformity within \(NC^ 1\)
• Polynomial size \(\Omega\)-branching programs and their computational power
• REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
• Some Remarks on Generalized Spectra
• Space-bounded reducibility among combinatorial problems
• Symmetric space-bounded computation
• The polynomial-time hierarchy
• The subgraph homeomorphism problem

Cited in

(16)

• A note on first-order projections and games.
• scientific article; zbMATH DE number 1301750 (Why is no real title available?)
• On completeness for NP via projection translations
• Does reductive proof theory have a viable rationale?
• Proof-theoretic reduction as a philosopher's tool
• Generalized hex and logical characterizations of polynomial space
• Languages represented by Boolean formulas
• Proving completeness by logic
• Complete problems for monotone NP
• REDUCTION TECHNIQUES FOR PROVING DECIDABILITY IN LOGICS AND THEIR MEET–COMBINATION
• Context-sensitive transitive closure operators
• Succinct representation, leaf languages, and projection reductions
• First-order reduction and computational complexity
• The problem of guaranteeing the existence of a complete set of reductions
• Checking Sufficient Completeness by Inductive Theorem Proving
• scientific article; zbMATH DE number 408812 (Why is no real title available?)

This page was built for publication: Methods for proving completeness via logical reductions

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