臺灣博碩士論文加值系統

在用輸入大小之多項式函數的時間內可解的問題中，有些是有很快的平行計算方法的
，所謂有很快的平行計算方法就是說這種問題可用輸入大小之多項式函數個處理器，
而在輸入大小之對數多項式函數時間內解決，我們通常稱這些問題所構成的集合為尼
克集。另外有些問題則是很可能沒有如此快的平行計算方法，以往，我們通常是利用
證明一個問題具有對數記憶體完備性來說明此一問題很不可能有如此快的平行計算方
法，但是我們發現有些問題很不可能在尼克集內，而且又很不能具有對數記憶體完備
性，所以我們提出一種新觀念稱為超尼克集問題難度，這個觀念可用來規範那些沒有
快的平行計算方法的問題，而且它也可規範上述那些用對數記憶體完備性所不能規範
之問題，我們也證明了所有用對數記憶體完備性所規範之問題都可用超尼克集問題難
度來規範，因此，在衡量平行計算方法之時間複雜度下，我們建議用此一新觀念來取
代舊有的對數記憶體完備性。

目錄
摘要
誌謝
Chapter 1 Introduction
Chapter 2 The Relation Between the Sequential Space Complexity and the Parallel Time Complexity
2.1 Log-Space Reducibility, Log-Space Completeness and the Uniform Circuit Family Model
2.2 The Original Meaning of Log-Space Completeness
2.3 The Relation Between the Sequential Space Complexity and the Parallel Time Complexity
Chapter 3 Log-Space Complete Problems and NC Problems
3.1 A Review of the Log-Space Complete Problems
3.2 The NC Problems
Chapter 4 The Concept of NC-Hardness
4.1 NCk Reducibility and NC-Hardness
4.2 The Implication of NC-Hardness
Chapter 5 Three NC-Hard Problems which Do Not Seem to Be Log-Space Complete
5.1 The Maximum Flow Size Problem with Subexponential Edge Capacities is NC-Hard
5.2 The Directed Graph k-Accessibility Problem and the Circuit Value Problem
Chapter 6 Using NCk Reduction Instead of Log-Space Reduction in Illustrating Problems which are Hard to Parallelize
6.1 The Circuit Value Problem is NC-Hard
6.2 The Monotone Circuit Value Problem is NC-Hard
6.3 The Problem of Finding the Lexicographically First Maximal Clique in an Undirected Graph is NC-Hard
Chapter 7 Concluding Remarks
References