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

Семейство универсальных попарно независимых хеш-функций

2010-05-07T19:28:05Z

Rinatvr: /* Лемма */

==Определение==
<tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется семейством универсальных попарно независимых хеш-функций, если для <tex> \forall x_1, x_2 \in 2^n, x_1 \ne x_2</tex> и <tex> \forall y_1, y_2 \in 2^k</tex> и равномерной выборки функции <tex> h \in H_{n, k} </tex> будет выполнено <tex>P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}</tex>

==Лемма==
Для любого <tex>n \in N </tex> существует <tex>H_{n, n}</tex>, что <tex> h_{a, b} = (ax+b)</tex> в поле <tex> \mathbb{F}_{2n}</tex> для любых <tex>a, b \in N</tex>

==Теорема==
Для любых <tex>n, k \in N</tex> существует <tex>H_{n, k}</tex>

===Доказательство===

Построим <tex>H_{n, k}</tex> следующим образом:

При <tex>n=k</tex> существование <tex>H_{n, k}</tex> следует из леммы.

При <tex>n < k </tex> получим переменную <tex> x' </tex> обрезав первые <tex>n-k</tex> бит переменной <tex>x</tex>. Тогда для переменной <tex>x'</tex> существует <tex>H_{n, n}</tex>, а для <tex>x</tex> - соответственно <tex>H_{n, k}</tex>.

При <tex>n > k </tex> получим <tex>H_{k, k}</tex>. <tex>H_{n, k}</tex> можно получить, обрезав значение хеш-функции из <tex>H_{k, k}</tex>, на первые <tex>n-k</tex> бит.

Семейство универсальных попарно независимых хеш-функций

2010-05-07T19:27:12Z

Rinatvr:

==Определение==
<tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется семейством универсальных попарно независимых хеш-функций, если для <tex> \forall x_1, x_2 \in 2^n, x_1 \ne x_2</tex> и <tex> \forall y_1, y_2 \in 2^k</tex> и равномерной выборки функции <tex> h \in H_{n, k} </tex> будет выполнено <tex>P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}</tex>

==Лемма==
Для любого <tex>n \in N </tex> существует <tex>H_{n, n}</tex>, что <tex> h_{a, b} = (ax+b)</tex> для любых <tex>a, b</tex> в поле <tex> \mathbb{F}_{2n}</tex>

==Теорема==
Для любых <tex>n, k \in N</tex> существует <tex>H_{n, k}</tex>

===Доказательство===

Построим <tex>H_{n, k}</tex> следующим образом:

При <tex>n=k</tex> существование <tex>H_{n, k}</tex> следует из леммы.

При <tex>n < k </tex> получим переменную <tex> x' </tex> обрезав первые <tex>n-k</tex> бит переменной <tex>x</tex>. Тогда для переменной <tex>x'</tex> существует <tex>H_{n, n}</tex>, а для <tex>x</tex> - соответственно <tex>H_{n, k}</tex>.

При <tex>n > k </tex> получим <tex>H_{k, k}</tex>. <tex>H_{n, k}</tex> можно получить, обрезав значение хеш-функции из <tex>H_{k, k}</tex>, на первые <tex>n-k</tex> бит.

Семейство универсальных попарно независимых хеш-функций

2010-05-05T19:32:23Z

Rinatvr:

Семейство универсальных попарно независимых хеш-функций

2010-05-05T19:31:46Z

Rinatvr: Новая страница: «==Определение== <tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется семейством универсальных попарно нез…»

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

2010-05-05T18:38:35Z

Rinatvr:

== Лекция 1 ==
*[[Класс DSPACE]]
*[[Класс DTIME]]
*[[Теорема о емкостной иерархии]]
*[[Теорема о временной иерархии]]
*[[Сведение по Карпу]]
*[[Сведение по Куку]]
*[[Класс P]]
*[[Класс NP]]
*[[Класс coNP]]

== Практика 1 ==
*[[Сведение по Куку задачи факторизации к языку из NP]]

== Лекция 2 ==
*[[Теорема Кука]]

== Практика 2 ==
*[[Понятие NP-трудной и NP-полной задачи]]
*[[NP-полнота задачи BH1N]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме КНФ]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]
*[[NP-полнота задачи о клике]]
*[[NP-полнота задачи о независимом множестве]]
*[[NP-полнота задачи о вершинном покрытии]]

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

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

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

== Лекция 4 ==
*[[Класс PS]]
*[[Теорема Сэвича]]
*[[PS-полнота задачи Generalized geography]]

== Лекция 6 ==
*Классы [[L]], [[NL]], [[NL-полнота|NLC]]
*[[NL-полнота задачи о достижимости в графе]]
*[[Классы EXP, NEXP. Полнота языков EXP и NEXP]]
*[[Теорема о связи вопросов EXP=NEXP и P=NP]]
*[[Теорема Иммермана]]

== Практика 6 ==
*[[Классы Sigma_i и Pi_i]]
*[[Класс PH]]
*[[Полиномиальная иерархия]]
*[[Теоремы о коллапсе полиномиальной иерархии]]

== Лекция 7 ==
*[[Теорема Карпа-Липтона]]

== Практика 7 ==
*[[Вероятностная машина Тьюринга]]
*[[Класс ZPP]]
*[[Сложностные классы RP и coRP]]
*[[Сложностный класс PP]]
*[[Сложностный класс BPP]]
*[[Уменьшение ошибки в классе RP, сильное и слабое определение]]

== Лекция 8 ==
*[[Теорема о включении BPP в P/poly]]
*[[Теорема Лаутемана]]
*[[Теорема Валианта-Вазирани]]

== Практика 8 ==
*[[Лемма Шварца-Зиппеля]]

== Лекция 9 ==
*[[Класс IP|Класс IP]]
*[[GNI|Принадлежность проблемы GNI классу IP]]
*[[Sharp SAT|#SAT]]

== Лекция 10 ==
*[[Семейство универсальных попарно независимых хеш-функций|Семейство универсальных попарно независимых хеш-функций]]

Класс PS

2010-04-01T13:30:24Z

Rinatvr: /* Класс NPS */

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

Заметим также, что
=== ''L'' ⊆ ''P'' ===
====Доказательство====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
----
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По [[Теорема о емкостной иерархии|теореме о емкостной иерархии]] <tex> L \neq PS </tex>. Так что хотя бы одно из рассмотренных включений — строгое, но неизвестно, какое. В настоящий момент общепринятая точка зрения, что все приведенные включения - строгие.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

В соответствии с [[Теорема Сэвича|теоремой Сэвича]] <tex>PS=NPS</tex>, поэтому обычно в теории сложности оперируют с классом <tex>PS</tex>.

Класс PS

2010-04-01T13:29:28Z

Rinatvr: /* Класс NPS */

Класс PS

2010-04-01T13:29:02Z

Rinatvr:

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

Заметим также, что
=== ''L'' ⊆ ''P'' ===
====Доказательство====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
----
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По [[Теорема о емкостной иерархии|теореме о емкостной иерархии]] <tex> L \neq PS </tex>. Так что хотя бы одно из рассмотренных включений — строгое, но неизвестно, какое. В настоящий момент общепринятая точка зрения, что все приведенные включения - строгие.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.
В соответствии с [[Теорема Сэвича|теоремой Сэвича]] <tex>PS=NPS</tex>, поэтому обычно в теории сложности оперируют с классом <tex>PS</tex>

Класс PS

2010-04-01T06:05:50Z

Rinatvr: /* Вывод */

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
----
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По [[Теорема о емкостной иерархии|теореме о емкостной иерархии]] <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений — строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T18:47:25Z

Rinatvr: /* Вывод */

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
----
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По теореме [[Теорема о емкостной иерархии|о емкостной иерархии]] <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений — строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T18:43:01Z

Rinatvr:

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
----
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По теореме [[Теорема о емкостной иерархии|о емкостной иерархии]] <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T18:42:28Z

Rinatvr:

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

----
=== Вывод ===
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По теореме [[Теорема о емкостной иерархии|о емкостной иерархии]] <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T18:37:25Z

Rinatvr: /* Вывод */

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По теореме [[Теорема о емкостной иерархии|о емкостной иерархии]] <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T18:33:46Z

Rinatvr:

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По теореме о емкостной иерархии <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T18:32:07Z

Rinatvr: /* Альтернативное определение */

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(in^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство:====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство:====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство:====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По теореме о емкостной иерархии <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T18:31:22Z

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

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(i*n^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство:====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство:====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство:====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По теореме о емкостной иерархии <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T18:28:23Z

Rinatvr:

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

Классом <tex>PS (PSPACE)\,\!</tex> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<tex>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </tex>, где <tex>m-\,\!</tex> детерминированная машина Тьюринга, <tex>S-\,\!</tex> расход памяти, <tex>|x|-\,\!</tex> длина <tex>x\,\!</tex>.

== Альтернативное определение ==
<tex> PS=\bigcup_{i=0}^\infty DSPACE(i*n^i)</tex>

== Связь класса ''PS'' с другими классами теории сложности ==

=== ''P'' ⊆ ''PS'' ===
====Доказательство:====

Машина Тьюринга <tex>m</tex>, распознающая язык из <tex>P</tex> за полиномиальную величину времени не успеет использовать память, размер которой превосходит полиномиальное значение.

=== ''NP'' ⊆ ''PS'' ===
====Доказательство:====

Для перебора всех сертификатов полиномиальной длины, необходим полиномиальный размер памяти. Тогда любой язык из <tex>NP</tex> принадлежит <tex>PS</tex>

=== ''L'' ⊆ ''P'' ===
====Доказательство:====

Машина Тьюринга, распознающая язык <tex>L=DSPACE(c \log n)</tex> работает не более чем: <tex>| \Sigma |^{c\log n}=poly(n) </tex> времени.

=== Вывод ===
<tex> L \subseteq P \subseteq NP \subseteq PS </tex>

По теореме о емкостной иерархии <tex> L \neq PS </tex>. Тогда одно из рассмотренных включений - строгое.

== Класс ''NPS'' ==

Классом <tex>NPS (NPSPACE)\,\!</tex> называется множество языков, распознаваемых недетерминированной машиной Тьюринга с полиномиально ограниченной памятью.

Класс PS

2010-03-31T17:42:08Z

Rinatvr:

Класс PS

2010-03-17T11:10:27Z

Rinatvr:

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

2010-03-17T09:36:02Z

Rinatvr: /* Лекция 4 */

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

== Практика 1 ==
*[[Сведение по Куку задачи факторизации к языку из NP]]

== Лекция 2 ==
*[[Теорема Кука]]

== Практика 2 ==
*[[Понятие NP-трудной и NP-полной задачи]]
*[[NP-полнота задачи BH1N]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]

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

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

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

== Лекция 4 ==
*[[Класс PS]]
*[[Теорема Сэвича]]
*[[PS-полнота задачи Generalized geography]]

Класс PS

2010-03-16T20:53:30Z

Rinatvr:

Класс PS

2010-03-16T19:43:18Z

Rinatvr:

Класс PS

2010-03-16T19:25:46Z

Rinatvr: Новая страница: «== Определение == Классом <math>PS (PSPACE)\,\!</math> называется множество языков, распознаваемых дете…»

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

Классом <math>PS (PSPACE)\,\!</math> называется множество языков, распознаваемых детерминированной машиной Тьюринга с полиномиально ограниченной памятью.

<math>PS=\{L \mid \exists \ m: L(m)=L, S(m, x) \le poly(|x|) \} </math>, где <math>m-\,\!</math> детерминированная машина Тьюринга, <math>S-\,\!</math> расход памяти, <math>|x|-\,\!</math> длина <math>x\,\!</math>.

== Альтернативное определение ==
<math> PS=\bigcup_{i=0}^\infty DSPACE(i*n^i)</math>

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

2010-03-16T18:56:07Z

Rinatvr:

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

== Практика 1 ==
*[[Сведение по Куку задачи факторизации к языку из NP]]

== Лекция 2 ==
*[[Теорема Кука]]

== Практика 2 ==
*[[Понятие NP-трудной и NP-полной задачи]]
*[[NP-полнота задачи BH1N]]
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]

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

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

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

== Лекция 4 ==
*[[Класс PS]]
*[[PS-полнота задачи Generalized geography]]