New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P

DOI10.1109/TC.1986.1676783zbMath0613.68023MaRDI QIDQ4720785

Roger A. Simons, Jeffrey Scott Vitter

Publication date: 1986

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmsunificationPRAMdepth-first searchunion-findrandom accessRAMWRAMfifth generationmonotone circuit valuepath system accessibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25)

Related Items (17)

A theory of strict P-completeness ⋮ Local consistency in parallel constraint satisfaction networks ⋮ Strict sequential P-completeness ⋮ Parallel computation of manipulator inverse dynamics ⋮ THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗† ⋮ Unification in Boolean rings ⋮ On the relationship of congruence closure and unification ⋮ Graph coloring on coarse grained multicomputers ⋮ A complexity theory of efficient parallel algorithms ⋮ Unifications, deunifications, and their complexity ⋮ Data independence of read, write, and control structures in PRAM computations ⋮ Efficient parallel term matching and anti-unification ⋮ A sublinear parallel algorithm for some dynamic programming problems ⋮ Deciding bisimilarity is P-complete ⋮ A theory of strict P-completeness ⋮ On the logic of unification ⋮ Boolean unification - the story so far

This page was built for publication: New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P