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

Теорема о ёмкостной иерархии

2010-03-15T16:53:01Z

Mashuna: /* Доказательство */

== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <math>f\,\!</math> и <math>g\,\!</math> таких, что <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, выполняется <math>DSPACE(g(n)) \ne DSPACE(f(n))</math>.

== Доказательство ==
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.

Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)\,\!</math> памяти <math>\}\,\!</math> .

Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина Тьюринга <math>m_0\,\!</math> такая, что <math>L(m_0)=L\,\!</math>.

Рассмотрим <math>m_0(<m_0,x>)\,\!</math>.

Пусть <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>. Тогда <math><m_0,x> \in L</math>, но в <math>L\,\!</math> по определению не может быть пары <math><m,x>\,\!</math>, которую допускает <math>m\,\!</math>. Таким образом, получаем противоречие.

Если <math>m_0\,\!</math> не допускает <math><m_0,x>\,\!</math>, то <math><m_0,x>\,\!</math> не принадлежит языку <math>L\,\!</math>. Это значит, что либо <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>, либо не допускает, используя памяти больше <math>f(|<m_0,x>|)\,\!</math>. Но <math>L \in DSPACE(f)</math>, поэтому <math>m_0\,\!</math> на любом входе <math>x\,\!</math> использует не более <math>f(|x|)\,\!</math> памяти. Получаем противоречие.

Следовательно такой машины не существует. Таким образом, <math>L \notin DSPACE(f)</math>.

<math>L \in DSPACE(g)</math>, так как можно проэмулировать машину Тьюринга <math>m_1\,\!</math> такую, что <math>L(m_1)=L\,\!</math>. Для каждой пары <math><m_3,x> \in L</math> рассмотрим <math>m_3(<m_3,x>)\,\!</math>. Если <math>m_3\,\!</math> завершила работу и не допустила, то <math>m_1\,\!</math> допускает <math><m_3,x>\,\!</math>. В другом случае не допускает. Так как любая такая машина использует памяти не более <math>f(|<m_3,x>|)\,\!</math>, а <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, <math>m_1\,\!</math> будет использовать памяти не более <math>g(|<m_3,x>|)\,\!</math>.

Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math> и <math>L \neq \empty</math>. Следовательно, <math>DSPACE(g(n)) \neq DSPACE(f(n))</math>

Теорема доказана.

Класс DSPACE

2010-03-12T21:12:00Z

Mashuna: /* Определение */

== Определение ==

Классом <math>DSPACE(f(n))\,\!</math> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)\,\!</math>, где <math>n\,\!</math> <math>-\,\!</math> длина входа.

<math>DSPACE(f(n)) = \{ L \mid \exists </math> машина Тьюринга <math>m : L(m)=L, \delta (m,x) \le f(|x|) \}</math>, где <math>|x|\,\!</math> <math>-\,\!</math> длина <math>x\,\!</math>.

Конструируемая по памяти функция

2010-03-12T21:01:42Z

Mashuna: /* Определение */

== Определение ==
Функция <math>f(x)\,\!</math> называется конструируемой по памяти, если можно вычислить <math>f(x)\,\!</math> по <math>x\,\!</math>, используя памяти не более <math>f(x)\,\!</math>.

Класс DSPACE

2010-03-12T20:59:26Z

Mashuna: /* Определение */

== Определение ==

Классом <math>DSPACE(f(n))\,\!</math> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)\,\!</math>, где <math>n\,\!</math> - длина входа.

<math>DSPACE(f(n)) = \{ L \mid \exists </math> машина Тьюринга <math>m : L(m)=L, \delta (m,x) \le f(|x|) \}</math>, где <math>|x|\,\!</math> - длина <math>x\,\!</math>.

Класс DSPACE

2010-03-12T20:57:22Z

Mashuna: /* Определение */

== Определение ==

Классом <math>DSPACE(f(n))\,\!</math> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)\,\!</math>

<math>DSPACE(f(n)) = \{ L \mid \exists </math> машина Тьюринга <math>m : L(m)=L, \delta (m,x) \le f(|x|) \}</math>

Теорема о ёмкостной иерархии

2010-03-12T20:55:59Z

Mashuna: /* Формулировка */

== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <math>f\,\!</math> и <math>g\,\!</math> таких, что <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, выполняется <math>DSPACE(g(n)) \ne DSPACE(f(n))</math>.

== Доказательство ==
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.

Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)\,\!</math> памяти <math>\}\,\!</math> .

Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина Тьюринга <math>m_0\,\!</math> такая, что <math>L(m_0)=L\,\!</math>.

Рассмотрим <math>m_0(<m_0,x>)\,\!</math>.

Пусть <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>. Тогда <math><m_0,x> \in L</math>, но в <math>L</math> по определению не может быть пары <math><m,x>\,\!</math>, которую допускает <math>m\,\!</math>. Таким образом, получаем противоречие.

Если <math>m_0\,\!</math> не допускает <math><m_0,x>\,\!</math>, то <math><m_0,x>\,\!</math> не принадлежит языку <math>L\,\!</math>. Это значит, что либо <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>, либо не допускает, используя памяти больше <math>f(|<m_0,x>|)\,\!</math>. Но <math>L \in DSPACE(f)</math>, поэтому <math>m_0\,\!</math> на любом входе <math>x\,\!</math> использует не более <math>f(|x|)\,\!</math> памяти. Получаем противоречие.

Следовательно такой машины не существует. Таким образом, <math>L \notin DSPACE(f)</math>.

<math>L \in DSPACE(g)</math>, так как можно проэмулировать машину Тьюринга <math>m_1\,\!</math> такую, что <math>L(m_1)=L\,\!</math>. Для каждой пары <math><m_3,x> \in L</math> рассмотрим <math>m_3(<m_3,x>)\,\!</math>. Если <math>m_3\,\!</math> завершила работу и не допустила, то <math>m_1\,\!</math> допускает <math><m_3,x>\,\!</math>. В другом случае не допускает. Так как любая такая машина использует памяти не более <math>f(|<m_3,x>|)\,\!</math>, а <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, <math>m_1\,\!</math> будет использовать памяти не более <math>g(|<m_3,x>|)\,\!</math>.

Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math> и <math>L \neq \empty</math>. Следовательно, <math>DSPACE(g(n)) \neq DSPACE(f(n))</math>

Теорема доказана.

Теорема о ёмкостной иерархии

2010-03-12T20:55:34Z

Mashuna: /* Доказательство */

== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <math>f</math> и <math>g</math> таких, что <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, выполняется <math>DSPACE(g(n)) \ne DSPACE(f(n))</math>.

== Доказательство ==
Зафиксируем <math>f\,\!</math> и <math>g\,\!</math>.

Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)\,\!</math> памяти <math>\}\,\!</math> .

Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина Тьюринга <math>m_0\,\!</math> такая, что <math>L(m_0)=L\,\!</math>.

Рассмотрим <math>m_0(<m_0,x>)\,\!</math>.

Пусть <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>. Тогда <math><m_0,x> \in L</math>, но в <math>L</math> по определению не может быть пары <math><m,x>\,\!</math>, которую допускает <math>m\,\!</math>. Таким образом, получаем противоречие.

Если <math>m_0\,\!</math> не допускает <math><m_0,x>\,\!</math>, то <math><m_0,x>\,\!</math> не принадлежит языку <math>L\,\!</math>. Это значит, что либо <math>m_0\,\!</math> допускает <math><m_0,x>\,\!</math>, либо не допускает, используя памяти больше <math>f(|<m_0,x>|)\,\!</math>. Но <math>L \in DSPACE(f)</math>, поэтому <math>m_0\,\!</math> на любом входе <math>x\,\!</math> использует не более <math>f(|x|)\,\!</math> памяти. Получаем противоречие.

Следовательно такой машины не существует. Таким образом, <math>L \notin DSPACE(f)</math>.

<math>L \in DSPACE(g)</math>, так как можно проэмулировать машину Тьюринга <math>m_1\,\!</math> такую, что <math>L(m_1)=L\,\!</math>. Для каждой пары <math><m_3,x> \in L</math> рассмотрим <math>m_3(<m_3,x>)\,\!</math>. Если <math>m_3\,\!</math> завершила работу и не допустила, то <math>m_1\,\!</math> допускает <math><m_3,x>\,\!</math>. В другом случае не допускает. Так как любая такая машина использует памяти не более <math>f(|<m_3,x>|)\,\!</math>, а <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, <math>m_1\,\!</math> будет использовать памяти не более <math>g(|<m_3,x>|)\,\!</math>.

Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math> и <math>L \neq \empty</math>. Следовательно, <math>DSPACE(g(n)) \neq DSPACE(f(n))</math>

Теорема доказана.

Теорема о ёмкостной иерархии

2010-03-12T19:38:57Z

Mashuna: /* Доказательство */

== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух [[Конструируемая по памяти функция|конструируемых по памяти функций]] <math>f</math> и <math>g</math> таких, что <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, выполняется <math>DSPACE(g(n)) \ne DSPACE(f(n))</math>.

== Доказательство ==
Зафиксируем <math>f</math> и <math>g</math>.

Рассмотрим язык <math>L = \{ <m,x> \mid m(<m,x>)</math> не допускает, используя не более <math> f(|<m,x>|)</math> памяти <math>\}</math> .

Пусть <math>L \in DSPACE(f)</math>, тогда для него есть машина тьюринга <math>m_0</math> такая, что <math>L(m_0)=L</math>.

Рассмотрим <math>m_0(<m_0,x>)</math>.

Пусть <math>m_0</math> допускает <math><m_0,x></math>. Тогда <math><m_0,x> \in L</math>, но в <math>L</math> по определению не может быть пары <math><m,x></math>, которую допускает <math>m</math>. Таким образом, получаем противоречие.

Если <math>m_0</math> не допускает <math><m_0,x></math>, то <math><m_0,x></math> не принадлежит языку <math>L</math>. Это значит, что либо <math>m_0</math> допускает <math><m_0,x></math>, либо не допускает, используя памяти больше <math>f(|<m_0,x>|)</math>. Но <math>L \in DSPACE(f)</math>, поэтому <math>m_0</math> на любом входе <math>x</math> использует не более <math>f(|x|)</math> памяти. Получаем противоречие.

Следовательно такой машины не существует. Таким образом, <math>L \notin DSPACE(f)</math>.

<math>L \in DSPACE(g)</math>, так как можно проэмулировать <math>m</math>.

Получается, что <math>L \in DSPACE(g(n)) \ DSPACE(f(n))</math>.

Теорема доказана.

Конструируемая по памяти функция

2010-03-12T17:58:37Z

Mashuna: /* Определение */

== Определение ==
Функция <math>f(x)</math> называется конструируемой по памяти, если можно вычислить <math>f(x)</math> по <math>x</math>, используя памяти <math>\le f(x)</math>.

Теорема о ёмкостной иерархии

2010-03-10T11:57:54Z

Mashuna: /* Доказательство */

Теорема о ёмкостной иерархии

2010-03-10T11:57:11Z

Mashuna: /* Доказательство */

Теорема о ёмкостной иерархии

2010-03-10T11:49:20Z

Mashuna: /* Доказательство */

Теорема о ёмкостной иерархии

2010-03-10T11:45:48Z

Mashuna: /* Доказательство */

Теорема о ёмкостной иерархии

2010-03-10T11:45:06Z

Mashuna: /* Доказательство */

Теорема о ёмкостной иерархии

2010-03-10T11:29:21Z

Mashuna: /* Формулировка */

Класс DSPACE

2010-03-10T10:29:00Z

Mashuna:

== Определение ==

Классом <math>DSPACE(f(n))</math> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)</math>

<math>DSPACE(f(n)) = \{ L \mid \exists </math> машина Тьюринга <math>m : L(m)=L, \delta (m,x) \le f(|x|) \}</math>

Теория сложности (старая трешовая версия)

2010-03-10T10:22:59Z

Mashuna: /* Лекция 1 */

== Лекция 1 ==
*[[Класс DSPACE]]
*[[Теорема о емкостной иерархии]]

== Лекция 3 ==
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бейкера-Гилла-Соловэя]]

== Практика 3 ==
*[[NP-полнота задачи о сумме подмножества]]
*[[NP-полнота задачи о рюкзаке]]

== Практика, которой на самом деле не было ==
*[[NP-полнота задачи о раскраске графа]]

Класс DSPACE

2010-03-10T10:22:36Z

Mashuna: переименовал «Классы DSPACE» в «Класс DSPACE»

Классом <math>DSPACE(f(n))</math> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <math>f(n)</math>

<math>DSPACE(f(n)) = \{ L \mid \exists </math> машина Тьюринга <math>m : L(m)=L, \delta (m,x) \le f(|x|) \}</math>

Классы DSPACE

2010-03-10T10:22:36Z

Mashuna: переименовал «Классы DSPACE» в «Класс DSPACE»

#перенаправление [[Класс DSPACE]]

Теория сложности (старая трешовая версия)

2010-03-10T10:20:33Z

Mashuna: /* Лекция 1 */

== Лекция 1 ==
*[[Классы DSPACE]]
*[[Теорема о емкостной иерархии]]

== Лекция 3 ==
*[[Теорема Ладнера]]
*[[Теорема Левина]]
*[[Теорема Бейкера-Гилла-Соловэя]]

== Практика 3 ==
*[[NP-полнота задачи о сумме подмножества]]
*[[NP-полнота задачи о рюкзаке]]

== Практика, которой на самом деле не было ==
*[[NP-полнота задачи о раскраске графа]]

Теория сложности (старая трешовая версия)

2010-03-10T10:19:37Z

Mashuna: /* Лекция 1 */

Конструируемая по памяти функция

2010-03-10T10:18:45Z

Mashuna: Новая страница: «== Определение == Функция <math>f(x)</math> называется конструируемой по памяти, если можно построи…»

== Определение ==
Функция <math>f(x)</math> называется конструируемой по памяти, если можно построить <math>f(x)</math> по <math>x</math>, используя памяти <math>\le f(x)</math>.

Теорема о ёмкостной иерархии

2010-03-10T10:15:53Z

Mashuna: /* Формулировка */

Теорема о ёмкостной иерархии

2010-03-10T09:17:28Z

Mashuna: /* Формулировка */

== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух конструируемых по памяти функций <math>f</math> и <math>g</math> таких, что <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, выполняется <math>DSPACE(g(n)) \ne DSPACE(f(n))</math>.

Теорема о ёмкостной иерархии

2010-03-10T09:16:59Z

Mashuna: Новая страница: «== Формулировка == '''Теорема о емкостной иерархии''' утверждает, что для любых двух конструир…»

== Формулировка ==
'''Теорема о емкостной иерархии''' утверждает, что для любых двух конструируемых по памяти функций <math>f</math> и <math>g</math> таких, что <math> \lim_{n \rightarrow \infty} f(n)/g(n) = 0</math>, dsgjkyztncz <math>DSPACE(g(n)) \ne DSPACE(f(n))</math>.