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