Введение
Набор задач, решаемых небольшими схемами.
В теории вычислительной сложности, P/poly — это класс сложности, представляющий задачи, которые могут быть решены с помощью небольших схем. Более точно, это множество формальных языков, имеющих семейство схем полиномиального размера. Его также можно определить эквивалентно с точки зрения машин Тьюринга с подсказками (advice), представляющих собой дополнительную информацию, предоставляемую машине Тьюринга вместе с ее входом, которая может зависеть от длины входа, но не от самого входа. В этой формулировке, P/poly — это класс задач принятия решений, которые могут быть решены машиной Тьюринга за полиномиальное время с использованием подсказок длиной, полиномиальной относительно размера входа. Эти два различных определения делают P/poly центральным понятием в сложности схем и неравномерной сложности. Например, популярный тест простоты Миллера — Рабина можно сформулировать как алгоритм P/poly: "подсказка" — это список кандидатов для проверки. Можно предварительно вычислить список значений таким образом, чтобы для каждого составного числа гарантированно существовал свидетель в этом списке. Например, для правильного определения простоты 32-битных чисел достаточно проверить существование коротких списков кандидатов в свидетели. Это следует из того факта, что для каждого составного числа три из четырех кандидатов успешно обнаруживают его составность. Отсюда, простой аргумент подсчета, аналогичный тому, что используется в доказательстве BPP ⊆ P/poly, показывает, что существует подходящий список кандидатов для каждого размера входа, и более того, что большинство достаточно длинных списков кандидатов будут работать правильно, хотя поиск списка, гарантированно работающего, может быть дорогостоящим.
In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non uniform complexity. For example, the popular Miller–Rabin primality test can be formulated as a P/poly algorithm: the "advice" is a list of candidate values to test. It is possible to precompute a list of values such that every composite bit number will be certain to have a witness in the list. For example, to correctly determine the primality of 32 bit numbers, it is enough to test The existence of short lists of candidate witnesses follows from the fact that for each composite , three out of four candidate values successfully detect that is composite. From this, a simple counting argument similar to the one in the proof that BPP P/poly below shows that there exists a suitable list of candidate values for every input size, and more strongly that most long enough lists of candidate values will work correctly, although finding a list that is guaranteed to work may be expensive.
Ограниченно-ошибочный вероятностный полином содержится в P/poly
Теорема Адлемана утверждает, что BPP ⊆ P/poly, где BPP – это класс задач, разрешимых рандомизированными алгоритмами с двусторонней ошибкой за полиномиальное время. Более слабый результат был первоначально доказан Леонардом Адлеманом, а именно, что RP ⊆ P/poly; и этот результат был обобщён до BPP ⊆ P/poly Беннеттом и Гиллом. Варианты теоремы показывают, что BPL содержится в L/poly, а AM содержится в NP/poly.