復雜性
編輯與標準的位置數字系統相比,單數系統很不方便,因此在實踐中不用于大型計算。它出現在理論計算機科學中的一些決策問題描述中(如一些P-complete問題),它被用來人為地減少問題的運行時間或空間要求。例如,整數分解問題被懷疑需要超過輸入長度的多項式函數作為運行時間,如果輸入是二進制的,但如果輸入是單進制的,它只需要線性運行時間。然而,這有可能是誤導。對于任何給定的數字來說,使用單數輸入都比較慢,而不是更快;區別在于二進制(或更大的基數)輸入與數字的基數2(或更大的基數)對數成正比,而單數輸入則與數字本身成正比。
因此,雖然單數的運行時間和空間要求作為輸入大小的函數看起來更好,但它并不代表一個更有效的解決方案。在計算復雜性理論中,單數被用來區分強NP不完全的問題和NP不完全但不是強NP不完全的問題。如果一個問題的輸入包括一些數字參數,即使通過用單數表示參數使輸入的大小人為地變大,它仍然是NP-完全的,那么這個問題就是強NP-完全的。對于這樣的問題,存在著所有參數值最多是多項式大的硬實例。
單一數字系統的應用
編輯單數編號被用作一些數據壓縮算法的一部分,如Golomb編碼。它也構成了Peano公理的基礎,用于在數理邏輯中實現算術的形式化。一種被稱為Church編碼的單數符號被用于在lambdacalculus中表示數字。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/164178/