Methods for proving completeness via logical reductions
DOI10.1016/0304-3975(93)90109-7zbMATH Open0777.68040OpenAlexW1976534954MaRDI QIDQ685391FDOQ685391
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
Recommendations
Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- On uniformity within \(NC^ 1\)
- A taxonomy of problems with fast parallel algorithms
- Nondeterministic Space is Closed under Complementation
- The polynomial-time hierarchy
- Comparing the Expressibility of Languages Formed Using NP-Complete Operators
- Languages that Capture Complexity Classes
- Bounded Query Classes
- Symmetric space-bounded computation
- The subgraph homeomorphism problem
- Space-bounded reducibility among combinatorial problems
- Maze recognizing automata and nondeterministic tape complexity
- Constant Depth Reducibility
- Title not available (Why is that?)
- A complexity theory based on Boolean algebra
- Polynomial size \(\Omega\)-branching programs and their computational power
- Complete problems for symmetric logspace involving free groups
- Title not available (Why is that?)
- Title not available (Why is that?)
- Complete Problems Involving Boolean Labelled Structures and Projection Transactions
- Title not available (Why is that?)
- Some Remarks on Generalized Spectra
- Title not available (Why is that?)
- Title not available (Why is that?)
- REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
Cited In (16)
- A note on first-order projections and games.
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
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)
