The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Lower Bounds in a Parallel Model Without Bit Operations
Ketan Mulmuley,
Pages. 1460-1509
Abstract
Contents 1. Overview
1.1. Introduction
1.2. The issue of bitlengths
1.3. Statement of the results
1.4. Basic idea of the proof
1.5. Organization of the paper
2. The model
2.1. PRAM without bit operations
2.2. Bit extraction
2.3. Complexity classes
3. Parametric versus parallel complexity
3.1. A general lower bound
3.2. s-t-mincuts in weighted undirected graphs
3.3. Global mincuts in weighted undirected graphs
4. Linear PRAM
4.1. The number of possible branchings
4.2. Parameterization
4.3. A lattice problem
5. PRAM without bit operations
5.1. The number of possible branchings
5.2. Parameterization
5.3. A lattice problem
6. Extensions
6.1. Randomized algorithms
6.2. PRAM with limited bit operations
6.3. The number of iterations in sequential algorithms
6.4. Weighted MAX-SNP problems
6.5. Higher order parametric complexity
7. The P versus NC problem
8. Conclusion
Key words computational complexity, parallel algorithms, lower bounds
Mathmatical Subject Classification 68Q05, 68Q15, 68Q22, 68Q25