e/Advice (complexity)

Information
has gloss	eng: In Computational complexity theory, an advice string is an extra input to a Turing machine which is allowed to depend on the length n of the input, but not on input itself. A decision problem is in the complexity class P/f(n) if there is a polynomial time Turing machine M with the following property: for any n, there is an advice string A of length f(n) such that, for any input x of length n, the machine M correctly decides the problem on the input x, given x and A.
lexicalization	eng: advice
instance of	e/Complexity class

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