Схемная сложность и класс P/poly

2012-05-07T12:49:13Z

109.188.214.160:

== Определения ==
{{Определение
|definition=
<tex>P/poly=\{L | \forall n </tex> существует логическая схема <tex> C_n </tex> с <tex> n </tex> входами и одним выходом такая, что:
#размеры <tex> C_n \leqslant p(n)</tex>, где <tex> p </tex> {{---}} полином;
#<tex>x \in L \iff C_{|x|}(x) = 1 \}</tex>.
}}

{{Определение
|definition=
Пусть C {{---}} сложностный класс, f {{---}} функция. Тогда <tex> C/f = \{L| </tex> существуют <tex> a_0, a_1, .. , a_n, .. </tex> {{---}} подсказки, программа p, удовлетворяющая ограничениям C:
#<tex>|a_i| \leqslant f(i) </tex>;
#<tex> x \in L \iff p(x, a_{|x|})=1 \}</tex>.
}}

{{Определение
|definition=
Пусть <tex> F = \{f_i\}</tex>. Тогда <tex> C/F = \bigcup\limits_{f \in F} C/f </tex>.
}}

== Теоремы ==

{{Теорема
|statement=
<tex> P \subset P/poly </tex>.
|proof=
<tex> L \in P \Rightarrow \exists </tex> машина Тьюринга m такая, что <tex> L(m)=L </tex>. Составим логическую схему для m, как мы сделали в [[Примеры_NP-полных_языков._Теорема_Кука|теореме Кука]]. Отсюда следует, что <tex> P \subset P/poly </tex>.
}}

{{Теорема
|statement=
Схемная сложность полином <tex> \subset P/poly</tex>.
|proof=
<tex> L \in </tex> схемная сложность полином. Тогда <tex> \exists C_0, C_1, .., C_n, .. </tex>. Запишем программу
<tex> p(x, C_{|x|}) </tex>:
'''return''' <tex>C_{|x|}(x) </tex>

Теорема выполняется.
}}

{{Теорема
|statement=
<tex> P/poly \subset </tex> схемная сложность полином.
|proof=
Пусть <tex> L \in P/poly </tex>. Тогда существуют <tex> a_0, a_1, .. , a_n, .. </tex> {{---}} подсказки. Зафиксируем n. Числу соответствует логическая схема <tex> C_n </tex>. Запишем программу p в виде логической схемы, которая принимает на вход слово длины n и подсказку <tex> a_n </tex>, за счет чего распознаваться будут только слова из языка. Зашьем подсказку в самой схеме, теперь она принимает только слова длины n и определяет их принадлежность языку.
}}

Викиконспекты - Вклад участника [ru]

Схемная сложность и класс P/poly