Abstract
循序演算法((sequential algorithms)與平行演算法(parallel algorithms) 的不同，在於循序演算法是每一步決策靠著前一決策的結果一步一步循序處理。然而當考慮到平行演算法時，問題要被分解，使得同時可以處理許多的子問題。當我們說一個問有好效率(feeicient) 的平行演算法時，意謂著我們可以用多項式數目(polnomial number)的處理單元，在多項式對數(poly-logarithmic)時間內解掉它。這篇論文討論了尼克集合(NC Class)與完整性對數空間集合(Logspace completeness) 。尼克集是一群擁有好效率的平行演算法的問題集合。而完整性對數空間集合問題集合裡的任一問題, 都可以把所有在p集合裡的問題對數簡化(log space reducible)到它。通常我們會說完整性對數空間集合問題是P集合里面最難的問題。論文的主要內容在研究的瑟夫問題(Josephus Prlblem)與其相關的問題。約瑟夫問題是一個古老的具體數學(concrete mathematics)問題，它已經有許多數學上的討論與循序演算法。我們論文在討論這問題的平行演算法。由這問題我們導出另外三類相關的問題，其中我們證明還復式約瑟夫問題(Inversion Josephus Problem)和約瑟夫問題可以互相作簡化(reducible) ，而另外的FORF問題與MFCVP 問題則是還復式約瑟夫問題的一般化。其中我們證明MFCVP 問題是完整性對數空間集合問題，而對FORF問題我們則發現，若其運算元具有轉結合律(Trans-associative) 性質，則這問題會落在尼克集當中，但同時我們也證明了還復式的瑟夫問題中的運算元mod 沒有轉結合率性質。這篇論文的主要結果在於找出問題原有的平行特性，并找到一些很難有好效率平行演算法的問題，另外提出一些相關的推測以提供討論的空間。