基本介紹
- 中文名：一元語言
- 本質：形式語言
理論,與其他複雜度類的關係,
理論
"一元"這個名字的起源來自於我們可以將一元語言視為將語言轉成自然數後，再以一進位系統轉出來產生的語言。既然所有語言的字串均可以視作有限字母的集合，故字串的集合必然屬於可數集。所以我們可以將任何語言內所有字串一一對應到一個自然數的集合A; 因此之故，我們可以知道，任何語言均有它的一元版本{1|k屬於A}。 相對應的，任何一元語言也可以變成它比較小型的二進制版本，只要我們將這一元語言的字串1對應到k的二進制表示法即可。
因為複雜度常常以輸入的字串長度來作基準，所以一個語言的"一元版本"常常會比較簡單。舉例來說，如果一個語言要花O(2)的時間來解讀，它的一元版本則需要O(n) 的時間，因為把語言的每個符號都換成"1"會讓這個語言的空間呈現對數比例的縮減。更廣義來說，如果一個語言可以用O(f(n))的時間以及O(g(n)) 的空間解讀，那他的一元版本解讀起來則需要O(n+ f(logn))的時間和O(g(logn))的空間 (多加的O(n)時間是因為我們起碼需要這些時間來讀取輸入字串)。 不過，如果一個語言是不可決定的, 那這個語言的一元版本也是不可決定的(沒有變得比較簡單)。
與其他複雜度類的關係
TALLY包含在P/poly內，因為我們可以對每一個k用一個一位元的建議字串來分辨1是否在這個語言中。任何一元語言都必然是屬於稀疏語言, 因為對任何自然數n，一元語言對長度為n的字串至多只有一個，所以對長度至多為n的字串也只有n個(合乎稀疏語言的定義)，但是並非所有的稀疏語言都是一元語言；因此TALLY包含在SPARSE裡面。 Piotr Berman 在1978年證明了若任何一元語言是NP-完全，則P = NP,Mahaney則將這個結果一般化到稀疏語言上面。
