The invariant problem for binary string structures and the parallel complexity theory of queries

DOI10.1016/0022-0000(92)90010-GzbMath0766.68043MaRDI QIDQ1191022

Steven Lindell

Publication date: 27 September 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

constant parallel time reducibilityparallel complexity theory of queriesstructure and complexity of database queries

Mathematics Subject Classification ID

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