Properties of complexity measures for PRAMs and WRAMs (Q580980): Difference between revisions

The computation of Boolean functions by parallel computers with shared memory (PRAMs and WRAMs) is considered. In particular, complexity measures for parallel computers like critical and sensitive complexity are compared with other complexity measures for Boolean functions like branching program depth and length of prime implicants and clauses. The relations between these complexity measures and their asymptotic behaviour are investigated for the classes of Boolean functions, monotone functions and symmetric functions.

0 references

Mathematics Subject Classification ID

68Q05

0 references

0 references

0 references

0 references

computation of Boolean functions

0 references

parallel computers with shared memory

0 references

PRAMs

0 references

WRAMs

0 references

complexity measures for parallel computers

0 references

complexity measures for Boolean functions

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0304-3975(86)90083-6

0 references

OpenAlex ID

W2064007242

0 references

cites work

Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

0 references

0 references

0 references

0 references

0 references

0 references

On recognizing graph properties from adjacency matrices

0 references

Q3674058

0 references

The critical complexity of graph properties

0 references

Trade-Offs between Depth and Width in Parallel Computation

0 references

Optimal decision trees and one-time-only branching programs for symmetric Boolean functions

0 references

The critical complexity of all (monotone) boolean functions and monotone graph properties

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:580980

@@ Property / author @@
-Ute Schuerfeld
@@ Property / author: Ute Schuerfeld / rank @@
-Normal rank
@@ Property / author @@
+Ute Schuerfeld
@@ Property / author: Ute Schuerfeld / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(86)90083-6
+Normal rank
@@ Property / OpenAlex ID @@
+W2064007242
@@ Property / OpenAlex ID: W2064007242 / rank @@
+Normal rank
@@ Property / cites work @@
+Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
+Normal rank
@@ Property / cites work @@
+Q3286850
@@ Property / cites work: Q3286850 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5538132
@@ Property / cites work: Q5538132 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3779735
@@ Property / cites work: Q3779735 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4193510
@@ Property / cites work: Q4193510 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3671891
@@ Property / cites work: Q3671891 / rank @@
+Normal rank
@@ Property / cites work @@
+On recognizing graph properties from adjacency matrices
+Normal rank
@@ Property / cites work @@
+Q3674058
@@ Property / cites work: Q3674058 / rank @@
+Normal rank
@@ Property / cites work @@
+The critical complexity of graph properties
@@ Property / cites work: The critical complexity of graph properties / rank @@
+Normal rank
@@ Property / cites work @@
+Trade-Offs between Depth and Width in Parallel Computation
+Normal rank
@@ Property / cites work @@
+Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
+Normal rank
@@ Property / cites work @@
+The critical complexity of all (monotone) boolean functions and monotone graph properties
+Normal rank