Methods for proving completeness via logical reductions
From MaRDI portal
Publication:685391
DOI10.1016/0304-3975(93)90109-7zbMath0777.68040OpenAlexW1976534954MaRDI QIDQ685391
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
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 (6)
Generalized hex and logical characterizations of polynomial space ⋮ Languages represented by Boolean formulas ⋮ A note on first-order projections and games. ⋮ Complete problems for monotone NP ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Context-sensitive transitive closure operators
Cites Work
- Polynomial size \(\Omega\)-branching programs and their computational power
- Symmetric space-bounded computation
- Complete problems for symmetric logspace involving free groups
- Space-bounded reducibility among combinatorial problems
- The polynomial-time hierarchy
- Maze recognizing automata and nondeterministic tape complexity
- On uniformity within \(NC^ 1\)
- Constant Depth Reducibility
- Comparing the Expressibility of Languages Formed Using NP-Complete Operators
- Bounded Query Classes
- A taxonomy of problems with fast parallel algorithms
- A complexity theory based on Boolean algebra
- Languages that Capture Complexity Classes
- Nondeterministic Space is Closed under Complementation
- Complete Problems Involving Boolean Labelled Structures and Projection Transactions
- Some Remarks on Generalized Spectra
- REFINING KNOWN RESULTS ON THE GENERALIZED WORD PROBLEM FOR FREE GROUPS
- The subgraph homeomorphism problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Methods for proving completeness via logical reductions
