The invariant problem for binary string structures and the parallel complexity theory of queries
From MaRDI portal
Publication:1191022
DOI10.1016/0022-0000(92)90010-GzbMath0766.68043MaRDI QIDQ1191022
Publication date: 27 September 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
constant parallel time reducibilityparallel complexity theory of queriesstructure and complexity of database queries
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Image approximations to electrostatic potentials in layered electrolytes/dielectrics and an ion-channel model, Diagonal forms of the translation operators in the fast multipole algorithm for scattering problems, A sixth-order image approximation to the ionic solvent induced reaction field, Covariances of the Dirac and Maxwell equations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The polynomial-time hierarchy
- The complexity of iterated multiplication
- Structure and complexity of relational queries
- On uniformity within \(NC^ 1\)
- An application of games to the completeness problem for formalized theories
- Simulation of Parallel Random Access Machines by Circuits
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- Relational queries computable in polynomial time
- Definability by constant-depth polynomial-size circuits
- Languages that Capture Complexity Classes
- Nondeterministic Space is Closed under Complementation
- The graph isomorphism disease
- Expressibility and Parallel Complexity