Материал из Викиконспекты
| НЕТ ВОЙНЕ
|
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
Антивоенный комитет России
|
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.
|
| Теорема (о емкостной иерархии): |
Пусть даны две функции [math]f[/math] и [math]g[/math] такие, что [math]\lim \limits_{n\rightarrow\infty} \frac{f(n)}{g(n)}=0[/math], тогда [math]DSPACE(f(n)) \neq DSPACE(g(n))[/math][1]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Для доказательства воспользуемся диагональным методом.
[2]
Рассмотрим функцию [math]h(n)=\sqrt{f(n)g(n)}[/math] и язык [math]L=\{x\bigm|x(x)\Bigr|_{S\leq h(|x|)}\neq 1\}[/math], где запись [math]S\leq h(|x|)[/math] означает, что программа запускается с лимитом памяти [math]h(|x|)[/math]. Иначе говоря, [math]L[/math] — это язык программ, которые не допускают собственный код, используя не более [math]h(|x|)[/math] памяти.
Докажем, что [math]L\in DSPACE(g(n))\setminus DSPACE(f(n))[/math].
- [math]L \in DSPACE(g(n))[/math]. Действительно, для проверки принадлежности программы [math]x[/math] языку достаточно запустить её с лимитом памяти [math]h(|x|)[/math] и проверить, что результат не равен 1. Тогда вся проверка будет выполнена с использованием не более [math]g(|x|)[/math] памяти в силу накладываемых ограничений.
- [math]L \notin DSPACE(f(n))[/math]. Пусть это не так, тогда существует программа [math]p[/math], распознающая язык [math]L[/math] и использующая не более [math]c \cdot f(n)[/math] памяти. Так как [math]f(n)=o(h(n))[/math], то [math]\exists n_0: \forall n\gt n_0 \Rightarrow c\cdot f(n)\lt h(n)[/math]. Будем считать, что [math]|p|\gt n_0[/math] (иначе добавим в программу пустые строки, искусственно увеличив её длину), тогда при вызове [math]p(p)[/math] потребуется не более [math]h(|p|)[/math] памяти. Выясним, принадлежит ли [math]p[/math] языку [math]L[/math]. Допустим, что [math]p\in L[/math], тогда [math]p(p)=1[/math], значит, [math]p\notin L[/math] по определению языка [math]L[/math]. Пусть теперь [math]p\notin L[/math]. Но тогда [math]p(p) \ne 1[/math], следовательно, [math]p\in L[/math].
Таким образом, язык [math]L[/math] не может быть из [math]DSPACE(f(n))[/math], следовательно, язык из [math]DSPACE(g(n))\setminus DSPACE(f(n))[/math] найден. |
| [math]\triangleleft[/math] |
| Теорема (о временной иерархии): |
Пусть даны две функции [math]f[/math] и [math]g[/math] такие, что [math]\lim \limits_{n\rightarrow\infty} \frac{Sim(f(n))}{g(n)}=0[/math], где [math]Sim(n)[/math] — время симуляции [math]n[/math] шагов одной машины Тьюринга на другой машине. Тогда [math]DTIME(f(n)) \neq DTIME(g(n))[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Доказательство аналогично доказательству теоремы о емкостной иерархии. При этом в отличие от памяти, время работы машины Тьюринга меньше, чем время ее симуляции на другой машине, из-за чего на соотношение [math]f[/math] и [math]g[/math] поставлено более сильное условие.
Положим [math]h(n)=Sim^{-1}(g(n))[/math], где [math]Sim^{-1}[/math] — обратная к времени симуляции функция, [math]L=\{x\bigm|x(x)\Bigr|_{T\leq h(|x|)}\neq 1\}[/math]. Тогда:
- [math]L \in DTIME(g(n))[/math], поскольку [math]Sim(h(n))=g(n)[/math], то есть запуск с ограничением [math]T \leq h(|x|)[/math] осуществляется за [math]O(g(n))[/math] времени;
- [math]L \notin DTIME(f(n))[/math] (доказывается аналогично соответствующему пункту предыдущей теоремы с учетом соотношения [math]f(n)=o(h(n))[/math]).
|
| [math]\triangleleft[/math] |
Примечания
- ↑ Строго говоря, теорема верна только для конструируемых по памяти функций [math]f[/math] и [math]g[/math]. Функция [math]f[/math] называется конструируемой по памяти, если можно вычислить ее значение, используя не более [math]f(x)[/math] памяти (см. [1]).
- ↑ Суть данного метода для набора множеств [math]\{A_x\}[/math] заключается в построении нового множества [math]B[/math] по принципу: [math]x \in B \Leftrightarrow x \notin A_x[/math] (в таком случае [math]A_x \neq B[/math] для любого [math]x[/math]). Аналогичный прием можно применять для набора функций [math]\{f_i\}[/math] путем построения новой функции [math]f':f'(x) \neq f_x(x)[/math]. Элементы [math]f_x(x)[/math] иногда называют диагональными, поскольку находятся на диагонали таблицы «функция — аргумент».
| |
[math]0[/math] |
[math]1[/math] |
[math]\cdots[/math]
|
| [math]f_0[/math] |
[math]\mathbf{f_0(0)}[/math] |
[math]f_0(1)[/math] |
[math]\cdots[/math]
|
| [math]f_1[/math] |
[math]f_1(0)[/math] |
[math]\mathbf{f_1(1)}[/math] |
[math]\cdots[/math]
|
| [math]\vdots[/math] |
[math]\vdots[/math] |
[math]\vdots[/math] |
[math]\ddots[/math]
|
Литература
- Sanjeev Arora, Boaz Barak — Computational Complexity: A Modern Approach — С. 69, 82. — 579 с. — ISBN 9780521424264
