Определение P - это язык, который может быть определен алгоритмом полиномиального времени. Определение P / poly может означать язык, который может быть определен схемой полиномиального размера (см. Http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Теперь, почему нельзя за полиномиальное время смоделировать схему полиномиального размера?
10
Ответы:
Дело в том, что в схеме есть фиксированное количество входов. Это означает, что для определения языка нам нужно семейство цепейС0, C1, C2, ... такое, что схема Ся сообщает вам, какие строки длины я есть в языке для каждого i . Для этого не требуется каких-либо отношений между цепями Ci и Ci+1 : они могут быть совершенно разными. В частности, для любого набора S⊆N вы могли бы установить объявление Ci=true , еслиi∈S иCi=false дляi∉S . Даже еслиS неразрешима!
Напротив, язык находится вP если существует одна машина Тьюринга, которая сообщает вам, есть ли каждый возможный ввод любой возможной длины в языке. Теперь вы не можете играть в забавные игры о входах разной длины.
Вы правы , что мы можем оценить любую фиксированную цепь вP . Но этого не обязательно достаточно, чтобы выбрать язык в P/poly . Чтобы сделать это, нам сначала нужно вычислить длину входа, затем использовать ее, чтобы определить, какую схему Ci нам нужно оценить, а затем оценить схему. Как показывает пример выше, часть «определить, какая схема» может даже не быть вычисляемой, не говоря уже о вычислимой за полиномиальное время.
источник