```An Introduction to
Parallel Computation
and
Ρ-Completeness Theory
by
Raymond Greenlaw
Joint work with:
Larry Ruzzo
Department of Computer Science
University of Washington
Jim Hoover
Computing Science Department
University of Alberta
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
1
Outline
•
•
•
•
•
•
•
Introduction
Parallel Models of Computation
Basic Complexity
Evidence that NC  Ρ
Ρ-Complete Problems
Comparator Circuit Class
Open Problems
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
2
Outline
•
•
•
•
•
•
•
Introduction
Parallel Models of Computation
Basic Complexity
Evidence that NC  Ρ
Ρ-Complete Problems
Comparator Circuit Class
Open Problems
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
3
Introduction
• Sequential computation:
Feasible ~ n O(1) time
(polynomial time).
• Parallel computation:
Feasible ~ n O(1) time and
~ n O(1) processors.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
4
Introduction
• Goal of parallel computation:
Develop extremely fast ((log n)O(1) )
time algorithms using a reasonable
number of processors.
• Speedup equation:
(best sequential time)  (parallel time).
(number of processors)
Allow a polynomial number of processors.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
5
Introduction
Roughly,
• A problem is feasible if it can be solved by a
parallel algorithm with worst case time and
processor complexity n O(1).
• A problem is feasible highly parallel if it can be
solved by an algorithm with worst case time
complexity (log n) O(1) and processor complexity
n O(1).
• A problem is inherently sequential if it is
feasible but has no feasible highly parallel
algorithm for its solution.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
6
Outline
•
•
•
•
•
•
•
Introduction
Parallel Models of Computation
Basic Complexity
Evidence that NC  Ρ
Ρ-Complete Problems
Comparator Circuit Class
Open Problems
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
7
Parallel Models of Computation
• Parallel Random Access Machine Model
• Boolean Circuit Model
• Circuits and PRAMs
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
8
Parallel Random Access Machine
RAM Processors
P0
P1
P2
C0
C1
C2
Global Memory Cells
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
9
Boolean Circuit Model
1 0
1 1
AND
OR
OR
AND
0
AND
OR
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
NOT
10
Circuits and PRAMS
Theorem:
A function f from {0,1}* to {0,1}* can be computed
by a logarithmic space uniform Boolean circuit family
{n } with depth (n) є (logn)O(1) and size (n ) є n O(1)
if and only if
f can be computed by a CREW-PRAM M on inputs of
length n in time t(n) є (logn)O(1) using p(n) є n O(1).
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
11
Outline
•
•
•
•
•
•
•
Introduction
Parallel Models of Computation
Basic Complexity
Evidence that NC  Ρ
Ρ-Complete Problems
Comparator Circuit Class
Open Problems
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
12
Basic Complexity
•
•
•
•
Decision, Function, and Search Problems
Complexity Classes
Reducibility
Completeness
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
13
Decision, Function, and Search Problems
4
3
Spanning Tree-D
4
6
3
4
6
3
4
Given: An undirected graph G = (V,E) with weights from N labeling edges in E and a
natural number k.
Problem: Is there a spanning tree of G with cost less than or equal to k ?
Spanning Tree-F
Given: Same (no k ).
Problem: Compute the weight of a minimum cost spanning tree.
Spanning Tree-S
Given: Same.
Problem: Find a minimum cost spanning tree.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
14
Complexity Classes
Definitions:
P is the set of all languages L that are decidable in sequential
time n O(1).
NC is the set of all languages L that are decidable in parallel time
(logn)O(1) and processors n O(1).
FP is the set of all functions from {0,1}* to {0,1}* that are
computable in sequential time n O(1).
FNC is the set of all functions from {0,1}* to {0,1}* that are
computable in parallel time (logn)O(1) and processors n O(1).
NC k, k  1, is the set of all languages L such that L is recognized by
a uniform Boolean circuit family {n } with size(n ) = n O(1) and
depth (n ) = O((logn)k ).
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
15
Many-One Reducibility
Definitions:
A language L is many-one reducible to a language L’, written
L mP L’ , if there is a function f such that x є L if and only if
f(x) є L’.
L is P many-one reducible to L’, written L mP L’ , if the function f is
in FP.
k
For k  1, L is NC k many-one reducible to L’, written L mNC L’, if
the function f is in FNC k.
L is NC many-one reducible to L’, written L mNC L’, if the function f
is in FNC.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
16
Many-One Reducibility
Lemma:
k
P
NC
The reducibilities m, m , m (k
 1), and mNC are transitive.
k
NC L’ then L є P.
– If L’ є P and L mP L’, L mNC L’ (k > 1), or L m
– If L’ є NC (k > 1), and L
k
k
NC

L’ then
m
L є NC k.
– If L’ є NC and L mNC L’ then L є NC .
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
17
Turing Reducibility
Definition:
L is NC Turing reducible to L’, written L TNC L’, if and only if the
L’-oracle PRAM on inputs of length n uses time (logn)O(1) and
processors n O(1).
Lemma:
The reducibility TNC is transitive.
– If L mNC L’ then L TNC L’.
– If L 
TNC L’ and L’ є NC then L є NC.
– If L TNC L’ and L’ є P then L є P.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
18
Completeness
Definitions:
A language L is P-hard under NC reducibility if L’ TNC L for
every L’ є P.
A language L is P-complete under NC reducibility if L є P and
L is P-hard.
Theorem:
If any P-complete problem is in NC then NC equals P.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
19
Outline
•
•
•
•
•
•
•
Introduction
Parallel Models of Computation
Basic Complexity
Evidence that NC  Ρ
Ρ-Complete Problems
Comparator Circuit Class
Open Problems
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
20
Evidence That NC  P
• General Simulations Are Not Fast
• Fast Simulations Are Not General
• Natural Approaches Provably Fail
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
21
Evidence That NC  P
Gaps in Simulations
Model
DTM
DTM
ATM
PDA
UC
PRAM
Resource
1
Resource
2
Time = n O(1)
Time = n O(1)
2Space = n O(1)
2Space = n O(1)
Size = n O(1)
Procs = n O(1)
Space
Reversals
log(Treesize)
log(Time)
Depth
Time
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
Max R2
C  NC
log n
(log n)O(1)
(log n)O(1)
(log n)O(1)
(log n)O(1)
(log n)O(1)
Min R2
CP
n O(1)
n O(1)
n O(1)
n O(1)
n O(1)
n O(1)
22
Outline
•
•
•
•
•
•
•
Introduction
Parallel Models of Computation
Basic Complexity
Evidence that NC  Ρ
Ρ-Complete Problems
Comparator Circuit Class
Open Problems
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
23
P-Complete Problems
There are approximately 175 P-complete
problems (500 with variations).
Categories:
–
–
–
–
Circuit complexity
Graph theory
Searching graphs
Combinatorial
optimization and flow
– Local optimality
– Logic
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
–
–
–
–
–
–
Formal languages
Algebra
Geometry
Real analysis
Games
Miscellaneous
24
Circuit Value Problem
Given:
An encoding  of a Boolean circuit , inputs x1,…,xn, and
a designated output y.
Problem:
Is output y of  TRUE on input x1,…,xn?
The Circuit Value Problem is P-complete under
reductions.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
1
NC
m
25
P-Complete Variations of CVP
– Topologically Ordered [Folklore]
– Monotone [Goldschlager 77]
– Alternating Monotone Fanin 2, Fanout 2
[Folklore]
– NAND [Folklore]
– Topologically Ordered NOR [Folklore]
– Synchronous Alternating Monotone Fanout 2
CVP [Greenlaw, Hoover, and Ruzzo 87]
– Planar [Goldschlager 77]
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
26
NAND Circuit Value Problem
Given:
An encoding  of a Boolean circuit  that consists solely of NAND
gates, inputs x1,…,xn, and a designated output y.
Problem:
Is output y of  TRUE on input x1,…,xn?
Theorem:
The NAND Circuit Value Problem is P-complete.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
27
NAND Circuit Value Problem
Proof:
Reduce AM2CVP to NAND CVP. Complement all inputs. Relabel all gates as
NAND.
1
0
0
OR
1
OR
1
0
0
1
1
NAND
1
1
NAND
1
AND
0
1
NAND
1
0
OR
1
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
NAND
1
28
Graph Theory
– Lexicographically First Maximal Independent Set
[Cook 85]
– Lexicographically First ( + 1)-Vertex Coloring
[Luby 84]
– High Degree Subgraph
[Anderson and Mayr 84]
– Nearest Neighbor Traveling Salesman Heuristic
[Kindervater, Lenstra, and Shmoys 89]
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
29
Lexicographically First Maximal Independent Set
Theorem: [Cook 85]
LFMIS is P-complete.
Proof:
Reduce TopNOR CVP to LFMIS. Add new vertex 0. Connect to all false
inputs.
1
1
1
2
0
0
3
0
4
NOR
5
NOR
6
X
X
X
1
2
0
3
4
5
7
0
6
1
NOR
8
X
7
8
0
NOR
9
0
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
9
30
Searching Graphs
– Lexicographically First Depth-First Search Ordering
[Reif 85]
[Greenlaw 92]
[Greenlaw 93]
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
31
Context-Free Grammar Empty
Given: A context-free grammar G=(N,T,P,S).
Problem: Is L(G) empty?
Theorem: [Jones and Laaser 76], [Goldschlager 81],
[Tompa 91]
CFGempty is P-complete.
Proof: Reduce Monotone CVP to CFGempty. Given 
construct G=(N,T,P,S) with N, T, S, and P as follows:
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
32
Context-Free Grammar Empty
N = {i | vi is a vertex in }
T = {a }
S = n, where vn is the output of .
P as follows:
1. For input vi, i  a if value of vi is 1,
2. i  jk if vi  vj Λ vk, and
3. i  j | k if vi  vj V vk .
* , where  є {a }+.
Then the value of vi is 1 if and only if i 
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
33
CFGempty Example
x1 = 0, x2 = 0, x3 = 1, and x4 = 1.
1
x1
x3 3
2 x2
5 OR
x4
4
AND 6
7 AND
G = (N, T, S, P), where
N = {1, 2, 3, 4, 5, 6, 7 }
T = {a }
S=7
P = {3  a, 4  a, 5  1 | 2, 6  34, 7  56}
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
34
Outline
•
•
•
•
•
•
•
Introduction
Parallel Models of Computation
Basic Complexity
Evidence that NC  Ρ
Ρ-Complete Problems
Comparator Circuit Class
Open Problems
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
35
Comparator Circuit Class
Definition: [Cook 82]
Comparator Circuit Value Problem (CCVP)
Given: An encoding  of a circuit  composed of
comparator gates, plus inputs x1,…,xn, and a
designated output y.
Problem: Is output y of  TRUE on input x1,…,xn?
Definition:
CC is the class of languages NC reducible to CCVP.
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
36
CC-Complete Problems
– Lexicographically First Maximal Matching
[Cook 82]
– Telephone Connection
[Ramachandran and Wang 91]
– Stable Marriage
[Mayr and Subramanian 92]
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
37
Outline
•
•
•
•
•
•
•
Introduction
Parallel Models of Computation
Basic Complexity
Evidence that NC  Ρ
Ρ-Complete Problems
Comparator Circuit Class
Open Problems
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
38
Open Problems
Find an NC algorithm or classify
as P-complete.
– Edge Ranking
– Edge-Weighted Matching
– Restricted Lexicographically First Maximal
Independent Set
– Integer Greatest Common Divisor
– Modular Powering
An Introduction to Parallel Computation and Ρ-Completeness Theory
Ray Greenlaw, Jim Hoover, and Larry Ruzzo
39
```