Схемная сложность — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Пусть <tex>\Sigma = \{0, 1\}</tex>.<br> Тогда язык <tex>L</tex> имеет <i>схемную сложность</i> <tex>f(n)</tex>, если <tex>\exi…»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 9: Строка 9:
  
 
==Следствие==
 
==Следствие==
Обозначим [[P\poly|<b><i>P\poly </i></b>]]<tex> = \{L | L </tex> имеет схемную сложность полином<tex>\}</tex><br>
+
Обозначим [[P by 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> P \subset </tex> <b><i>P\poly</i></b>

Текущая версия на 19:33, 4 сентября 2022

Пусть [math]\Sigma = \{0, 1\}[/math].
Тогда язык [math]L[/math] имеет схемную сложность [math]f(n)[/math], если [math]\exists c_1, c_2, \ldots c_n, \ldots [/math] - логические схемы, такие что

  1. [math]c_i[/math] имеет [math]i[/math] входов и один выход
  2. количество логических элементов в схеме [math]c_i[/math] равно [math]|c_i| \le f(i)[/math]
  3. [math]\forall x ~c_{|x|}(x) = 1 \Leftrightarrow x \in L [/math]

Утверждение

Если [math] L \in DTIME(f(n))[/math], то [math]L[/math] имеет схемную сложность [math]O(f(n)^2)[/math]

Следствие

Обозначим P\poly [math] = \{L | L [/math] имеет схемную сложность полином[math]\}[/math]
Тогда [math] P \subset [/math] P\poly