Схемная сложность

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Пусть [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