建议 (复杂度)

在复杂度类里面, 一个建议字串是一种以原本输入的长度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为有多项式长度建议字串的决定型对数空间。