Изменения
Новая страница: «Пусть <tex>\Sigma = \{0, 1\}</tex>.<br> Тогда язык <tex>L</tex> имеет <i>схемную сложность</i> <tex>f(n)</tex>, если <tex>\exi…»
Пусть <tex>\Sigma = \{0, 1\}</tex>.<br>
Тогда язык <tex>L</tex> имеет <i>схемную сложность</i> <tex>f(n)</tex>, если <tex>\exists c_1, c_2, \ldots c_n, \ldots </tex> - логические схемы, такие что
# <tex>c_i</tex> имеет <tex>i</tex> входов и один выход
# количество логических элементов в схеме <tex>c_i</tex> равно <tex>|c_i| \le f(i)</tex>
# <tex>\forall x ~c_{|x|}(x) = 1 \Leftrightarrow x \in L </tex>
==Утверждение==
Если <tex> L \in DTIME(f(n))</tex>, то <tex>L</tex> имеет схемную сложность <tex>O(f(n)^2)</tex>
==Следствие==
Обозначим [[P\poly|<b><i>P\poly </i></b>]]<tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex><br>
Тогда <tex> P \subset </tex> <b><i>P\poly</i></b>
Тогда язык <tex>L</tex> имеет <i>схемную сложность</i> <tex>f(n)</tex>, если <tex>\exists c_1, c_2, \ldots c_n, \ldots </tex> - логические схемы, такие что
# <tex>c_i</tex> имеет <tex>i</tex> входов и один выход
# количество логических элементов в схеме <tex>c_i</tex> равно <tex>|c_i| \le f(i)</tex>
# <tex>\forall x ~c_{|x|}(x) = 1 \Leftrightarrow x \in L </tex>
==Утверждение==
Если <tex> L \in DTIME(f(n))</tex>, то <tex>L</tex> имеет схемную сложность <tex>O(f(n)^2)</tex>
==Следствие==
Обозначим [[P\poly|<b><i>P\poly </i></b>]]<tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex><br>
Тогда <tex> P \subset </tex> <b><i>P\poly</i></b>
