建議 (複雜度)

在複雜度類裡面, 一個建議字串是一種以原本輸入的長度n來對圖靈機新增加的輸入，並且不是輸入的資料本身。如果存在一個多項式時間圖靈機具有特性如下：對任何自然數n，存在一個建議字串A，長度是f(n)，並且對任何長度是n的輸入x，機器M在給予x和A為輸入的狀態下可以正確判斷x是否在這個問題上正確，我們說這個決定型問題在複雜度類 P/f(n)裡面。

與建議字串有關最常見的複雜度類是P/poly，這個複雜度類包含建議字串的長度f(n)屬於任何n的多項式的語言。P/poly等同於以下這個複雜度類：對任何n，均存在一個n的多項式大小的布林線路，可以正確決定任何長度為n的輸入。這個等式其中一個方向的推論比較明顯：如果，對任何n，均存在一個多項式大小的布林線路A(n) 可以決定這問題，那我們可以用一個字串代表布林線路，然後圖靈機模擬布林線路的運作。如此一來，則對這問題來說，任何輸入長度為n的話，我們就有一個包含建議字串A(n)的圖靈機可以作正確的決定。等式另一個方向的證明則是先使用了Cook-Levin 理論，推論出我們可以用一個多項式時間的布林線路來模擬一個多項式時間的圖靈機。然後我們注意到，模擬一個有建議字串的圖靈機並不比模擬一個普通的圖靈機來得更難，因為我們可以將建議字串整個包含在線路裡面(因為建議字串是n的多項式大小)。這樣的話，這個方向的等式也成立了。

因為這個恆等式的關係，P/poly有時候我們以以能夠被多項式大小布林線路決定的題目來定義，或者是能被多項式大小非均勻布林線路解決的線路。

P/poly包含了P和BPP。它也包含了一些 不可決定的問題，例如說一些不可決定語言的一元版本，包含了停機問題。因此，對任何f(n)，P/poly不包含在DTIME (f(n))或者NTIME (f(n))裡面。

不只有P可以被用來增加建議字串變成新的複雜度類。舉例說來，我們可以將具有長度為f(n)建議字串的非決定多項式時間圖靈機定義為複雜度類NP/f(n)。

如果我們允許2ⁿ這麼長的建議字串，那我們就可以把n這個長度的所有可能輸入值跟對應的答案都寫入這個建議字串內。因此，我們知道任何函式在建議字串長度為2ⁿ的條件下一定是可以計算的，所以超過指數長度的建議字串是沒有意義的。

相同的，我們可以定義出L/poly為有多項式長度建議字串的決定型對數空間。