一千萬個為什麽

搜索

復雜性類對應於排序

TCS的兩個部分是算法和復雜性。我簡單地說算法是對上界的研究,表明你可以做某事(使用給定的受限資源),並且復雜性是關於顯示你不能做它沒有一些最小的資源。

因此,通常在決策模型中陳述算法問題,以便將其置於復雜性類中。

但總是困擾我的是,一些基本算法從未被提及為屬於特定類。一個例子是(比較)排序。盡我所能,一個相關的類看起來太缺乏了(真的,它只是在logspace中檢查結果是否排序?這看起來太弱了,或者我沒有得到正確的決策版本)。

比較排序所處的最佳/最合適/最有用的復雜性類是什麽?

最佳答案

對於 $ \ mathsf {TC} ^ 0 $ ($以下),排序問題實際上是完整的 \ {mathsf AC} ^ 0 $ - 還原)。標準來源是 Vollmer的書的第1.4.3節。

請註意$ \ mathsf {TC} ^ 0 $是決策問題的類,但我們通常認為排序是一個函數問題,即我們想要以非遞減順序輸出數字。但是,我們也可以將排序定義為決策問題,如下所示:

Given a sequence of numbers $a_1,\ldots,a_n$ and two numbers $k,p\in [n]$, we want to decide if $a_k$ is at position $p$ in the sequence we get by sorting $a_1,\ldots,a_n$ in nondecreasing order. Note that to avoid ambiguity, when $a_i=a_j$, we want $a_i$ to precede $a_j$ if $i

轉載註明原文: 復雜性類對應於排序