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 CP 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? Theorem: [Ladner 75] 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] – Stack Breadth-First Search [Greenlaw 92] – Breadth-Depth Search [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

Descargar
# Document