Почему P и P / poly тривиально не одинаковы?

10

Определение P - это язык, который может быть определен алгоритмом полиномиального времени. Определение P / poly может означать язык, который может быть определен схемой полиномиального размера (см. Http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Теперь, почему нельзя за полиномиальное время смоделировать схему полиномиального размера?

DCW
источник
4
P / poly может вычислять неразрешимые языки (упражнение).
Юваль
Спасибо, но что не так с моим аргументом - что схема полиномиального размера может быть смоделирована за полиномиальное время?
DCW
3
Это не правильно. Схемы полиномиального размера для разных входных длин могут быть радикально разными, и поэтому их нельзя описать одной машиной Тьюринга.
Yuval
Спасибо, но где в определении P говорится, что мы ограничены одной машиной Тьюринга? Все определения, которые я видел, похожи на mathworld.wolfram.com/PolynomialTime.html
dcw
3
@dcw Язык в P , если есть машина Тьюринга так , что ...
Дэвид Richerby

Ответы:

19

Дело в том, что в схеме есть фиксированное количество входов. Это означает, что для определения языка нам нужно семейство цепей C0,C1,C2, такое, что схема  Ci сообщает вам, какие строки длины  i есть в языке для каждого  i . Для этого не требуется каких-либо отношений между цепями Ci и  Ci+1 : они могут быть совершенно разными. В частности, для любого набора  SN вы могли бы установить объявление Ci=true , еслиiS иCi=false дляiS . Даже еслиS  неразрешима!

Напротив, язык находится в  P если существует одна машина Тьюринга, которая сообщает вам, есть ли каждый возможный ввод любой возможной длины в языке. Теперь вы не можете играть в забавные игры о входах разной длины.

Вы правы , что мы можем оценить любую фиксированную цепь в  P . Но этого не обязательно достаточно, чтобы выбрать язык в P/poly . Чтобы сделать это, нам сначала нужно вычислить длину входа, затем использовать ее, чтобы определить, какую схему  Ci нам нужно оценить, а затем оценить схему. Как показывает пример выше, часть «определить, какая схема» может даже не быть вычисляемой, не говоря уже о вычислимой за полиномиальное время.

Дэвид Ричерби
источник
1
P/poly