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

Аффинное пространство

2016-12-12T23:04:49Z

217.118.78.110: /* Аффинная независимость и базисы */

==Введение==
===Мотивация===
Рассмотрим векторное пространство <math>\mathbb{R}^3</math>, построим в нём плоскости <math>P_1=\{z=0\}</math> и <math>P_2=\{z=1\}</math>.
Плоскость <math>P_1</math> является векторным подпространством исходного векторного пространства,
а плоскость <math>P_2</math> не является.
Это довольно странно, так как с точки зрения геометрии ни одна из плоскостей ничем не лучше другой,
плоскость <math>P_2</math> интуитивно выражается той же линейной структурой, что и <math>P_1</math>.

В векторном пространстве недостаток плоскости <math>P_2</math> состоит в том, что у неё нет выделенного начала,
а <math>P_1</math> повезло пройти через точку <math>(0; 0; 0)</math>.
То, что проходящие через начало координат прямые и плоскости чем-то особенны, довольно неудобно.
Аффинные пространства исправляют это досадное недоразумение.

===Неформальное описание===
Аффинное пространство можно воспринимать как векторное пространство, в котором потеряли начальную точку.

Представим, что Алиса знает настоящую начальную точку, а Боб думает, что начальная точка это <math>p</math>.
Есть какие-то два вектора <math>a</math> и <math>b</math>, и Алиса с Бобом их складывают.
Алиса, опираяющаяся на настоящую начальную точку, получит <math>a + b</math>,
а Боб, откладывая те же вектора от точки <math>p</math>, получит
<math>p + (a - p) + (b - p)</math>,
понятно, что результаты будут разные.

Точно так же они могут вычислять линейные комбинации этих векторов, и, как правило, получать разные результаты.
Однако, если сумма коэффициентов линейной комбинации будет равна <math>1</math>, то результаты будут получаться одинаковые.
Алиса будет получать получать
<math>\lambda a + (1 - \lambda) b</math>,
и Боб будет точно так же получать
<math>p + \lambda(a - p) + (1 - \lambda)(b - p) = \lambda a + (1 - \lambda) b</math>.

На самом деле, точки, получаемые таким образом, будут лежать на прямой, проходящей через точки <math>a</math> и <math>b</math>.

У Боба с Алисой есть знание об "аффинной структуре" пространства, то есть значения аффинных комбинаций,
определённых как линейные комбинации в которых сумма коэффициентов равна <math>1</math>.
Пространство с аффинной структурой и есть аффинное пространство.

==Векторные пространства и определители==
Вспомним несколько фактов из линейной алгебры.
{{Определение
|definition=Набор векторов <math>\{\vec{e}_i\}_{i=1}^n</math> называется '''линейно независимым''' (ЛНЗ), если его линейная комбинация <math>\sum_{i=1}^n \alpha_i \vec{e}_i</math> равна нулю только в том случае, если она тривиальная, то есть <math>\forall i : \alpha_i = 0</math>.
}}{{Определение
|definition=Векторное пространство называется <math>d</math>-мерным, если в нём существует набор из <math>d</math> линейно независимых векторов,
и не существует набора из <math>d + 1</math> линейно независимого вектора.
}}
===Единственность разложения в базис===

{{Утверждение
|id=vectorUniqueness
|statement=В <math>d</math>-мерном пространстве любой вектор <math>\vec{A}</math> единственным образом раскладывается в базисе из <math>d</math> линейно независимых векторов <math>\{\vec{e}_i\}_{i=1}^d</math> как <math>\sum_{i=1}^d\alpha_i\vec{e}_i</math>.
|proof=Если мы добавим в базис вектор <math>\vec{A}</math>, то он обязательно станет линейно зависимым, и, значит, найдутся такие <math>\beta</math> и <math>\{\alpha_i\}</math>, что

<math>\displaystyle \beta \vec{A} + \sum_{i=1}^d\alpha_i\vec{e}_i=0 \implies
\vec{A} = \sum\limits_{i=1}^d-\frac{\alpha_i}{\beta}\vec{e}_i</math>,

и, значит, разложение существует.

Теперь пусть есть два разложения <math>\sum_{i=1}^d\alpha_i\vec{e}_i=\vec{A}</math> и <math>\sum_{i=1}^d\beta_i\vec{e}_i=\vec{A}</math>.
Тогда

<math>\displaystyle \vec{A} - \vec{A} = \vec{0} = \sum_{i=1}^d(\alpha_i - \beta_i)\vec{e}_i</math>,

однако такое может быть только в том случае, если линейная комбинация тривиальная, то есть
<math>\alpha_i - \beta_i = 0 \implies \alpha_i = \beta_i \implies</math>   разложение единственно.
}}

===Матрица перехода===

Мы можем переходить из одного базиса в другой.
Пусть у нас есть базисы <math>\{\vec{e}_i\}_{i=1}^d</math> и <math>\{\vec{f}_i\}_{i=1}^d</math>.

<math>\displaystyle
\vec{A} = \sum_{i=1}^d\alpha_i\vec{e}_i = \sum_{i=1}^d\beta_i\vec{f}_i \\
\vec{e}_i = \sum_{j=1}^d c_{ij}\vec{f}_j \\
\vec{A} = \sum_{i=1}^d\alpha_i\vec{e}_i =
\sum_{i=1}^d \alpha_i \sum_{j=1}^d c_{ij} \vec{f}_j =
\sum_{j=1}^d \vec{f}_j \sum_{i=1}^d \alpha_i c_{ij} \\
\beta_j = \sum_{i=1}^d\alpha_i c_{ij} \implies
\begin{pmatrix} \beta_1 \\ \beta_2 \\ \vdots \\ \beta_d \end{pmatrix} =
\begin{pmatrix}
c_{11} & c_{21} & \cdots & c_{d1} \\
c_{12} & c_{22} & \cdots & c_{d2} \\
\vdots & \vdots & \ddots & \vdots \\
c_{1d} & c_{2d} & \cdots & c_{dd}
\end{pmatrix}
\cdot
\begin{pmatrix} \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_d \end{pmatrix}
</math>

===Определитель===

Следующий факт позволяет красиво записывать один подозрительно часто появляющийся определитель.

<math> \displaystyle
\begin{vmatrix}
a_1 - p \\ a_2 - p \\ \vdots \\ a_n - p
\end{vmatrix}
= \begin{vmatrix}
a_1 - p & 0 \\ a_2 - p & 0 \\ \vdots & \vdots \\ a_n - p & 0 \\ p & 1
\end{vmatrix}
= \begin{vmatrix}
a_1 & 1 \\ a_2 & 1 \\ \vdots & \vdots \\ a_n & 1 \\ p & 1
\end{vmatrix}
</math>

==Аффинные пространства==
{{Определение
|definition='''Аффинное пространство''' — это либо вырожденное пустое множество, либо кортеж <math>\langle A, V, (+)\rangle</math>, состоящий из непустого множества точек <math>A</math>, векторного пространства <math>V</math> и действия <math>(+) : A \times V \rightarrow A</math>, удовлетворяющего следующим свойствам:
# <math>\forall a \in A : a + 0 = a</math>;
# <math>\forall v, w \in V, a \in A : (a + v) + w = a + (v + w)</math>;
# Для всех <math>a</math> из <math>A</math> отображение <math>(a+)</math> биективно.
}}
Из этих свойств также следует, что для всех <math>v</math> из <math>V</math> <math>(+v)</math> тоже биективно.

Последнее свойство позволяет определить вычитание двух элементов из <math>A</math>.
Пусть <math>a, b \in A</math>, тогда <math>b - a</math>, или <math>\overrightarrow{ab}</math>, это такой вектор из <math>V</math>, что <math>a + (b - a) = b</math>.
Таким образом определённое вычитание обладает следующими свойствами:
# <math>\forall a \in A, v \in V \ \exists ! b \in A : (b - a) = v</math>;
# <math>\forall a, b, c \in A : (b - a) + (c - b) = (c - a)</math>.
Далее для удобства будем пользоваться вторым вариантом записи.
{{Определение
|definition='''Размерность''' аффинного пространства <math>\langle A, V, (+)\rangle</math> равна размерности <math>V</math>.
}}
===Аффинные комбинации===
В векторном пространстве мы часто пользовались линейными комбинациями.
Давайте введём похожее определение для аффинного пространства.
Пусть у нас есть множество точек <math>\{a_i\}_{i=1}^n</math> из <math>A</math>
и такое множество скаляров <math>\{\lambda_i\}_{i=1}^n</math>, что <math>\sum_{i=1}^n \lambda_i = 1</math>.
Теперь давайте перебирать точки начала отсчёта <math>x \in A</math>,
и считать суммы <math>x + \sum_{i=1}^n \lambda_i \cdot \overrightarrow{xa_i}</math>.
Несложно показать, что

<math>\displaystyle \forall x, y \in A :
x + \sum_{i=1}^n \lambda_i \cdot \overrightarrow{xa_i} =
y + \sum_{i=1}^n \lambda_i \cdot \overrightarrow{ya_i}</math>.

То есть, какую бы точку мы не взяли за начало отсчёта, результат мы будем получать один и тот же.
{{Определение
|definition=Для любого набора точек <math>\{a_i\}_{i=1}^n</math> из <math>A</math> и такого набора скаляров <math>\{\lambda_i\}_{i=1}^n</math>, что <math>\sum_{i=1}^n \lambda_i = 1</math>, точка

<math>\displaystyle p = x + \sum_{i=1}^n \lambda_i \cdot \overrightarrow{xa_i}</math>,

не зависящая от выбора <math>x \in A</math>, называется '''аффинной комбинацией''' (а также ''барицентрической комбинацией'', или ''барицентром'') точек <math>\{a_i\}_{i=1}^n</math> с весами <math>\{\lambda_i\}_{i=1}^n</math>, и обозначается как

<math>\displaystyle p = \sum_{i=1}^n \lambda_i a_i</math>.
}}
===Аффинные подпространства===
С помощью этого определения довольно естественно ввести следующее определение аффинного подпространства.
{{Определение
|definition=Если <math>\langle A, V, (+)\rangle</math> — это аффинное пространство, то <math>B \subset A</math> является '''аффинным подпространством''' пространства <math>\langle A, V, (+)\rangle</math>, если любая аффинная комбинация любого множества точек из <math>B</math> принадлежит <math>B</math>.
}}
Например, <math>\{z=1\}</math> будет аффинным подпространством аффинного пространства над <math>\mathbb{R}^3</math>,
и прямая <math>ax+by=c</math> будет аффинным подпространством аффинного пространства над <math>\mathbb{R}^2</math>.

Следующая лемма проводит связь между аффинными подпространствами и векторными подпространствами.
{{Лемма
|statement=Пусть <math>\langle A, V, (+)\rangle</math> — это аффинное пространство.
# Непустое <math>B \subset A</math> является аффинным подпространством тогда и только тогда, когда для любой точки <math>a \in B</math> множество <math>W_a = \{\overrightarrow{ab} : b \in B\}</math> является подпространством <math>V</math>. Как следствие, <math>B=\{a + w : w \in W_a \}</math>. Более того, <math>W = \{\overrightarrow{ab} : a, b \in B\}</math> является подпространством <math>V</math>, и для любой точки <math>a \in B</math> справедливо <math>W_a = W</math>.
# Для любого <math>W</math>, являющегося подпространством <math>V</math>, множество <math>\{a + v : v \in W\}</math> является аффинным подпространством для любого <math>a \in A</math>.
}}

===Аффинная независимость и базисы===
Аналогично с линейной независимостью в векторных пространствах можно ввести аффинную независимость.
{{Лемма
|statement=Пусть <math>\langle A, V, (+)\rangle</math> — это аффинное пространство. Пусть <math>\{a_i\}_{i \in I}</math> — множество точек из <math>A</math>. Если для какого-то <math>i \in I</math> множество векторов <math>\{\overrightarrow{a_i a_j}\}_{j \in I \setminus \{i\}}</math> линейно независимо, то для любого <math>i \in I</math> множество <math>\{\overrightarrow{a_i a_j}\}_{j \in I \setminus \{i\}}</math> будет линейно независимо.
|proof=Пусть для какого-то <math>i \in I</math> множество векторов <math>\{\overrightarrow{a_i a_j}\}_{j \in I \setminus \{i\}}</math> линейно независимо, <math>k \in I</math> и пусть есть такой набор <math>\{\lambda_j\}_{j \in I \setminus \{k\}}</math>, что

<math>\displaystyle \sum_{j \in I \setminus \{k\}} \lambda_j \cdot \overrightarrow{a_k a_j} = 0</math>.

Поскольку <math>\overrightarrow{a_k a_j} = \overrightarrow{a_k a_i} + \overrightarrow{a_i a_j}</math>, мы имеем

<math> \displaystyle
\begin{aligned}
\sum_{j \in I \setminus \{k\}} \lambda_j \cdot \overrightarrow{a_k a_j} &=
\sum_{j \in I \setminus \{k\}} \lambda_j \cdot \overrightarrow{a_k a_i} + \sum_{j \in I \setminus \{k\}} \lambda_j \cdot \overrightarrow{a_i a_j} \\
&= \sum_{j \in I \setminus \{k\}} \lambda_j \cdot \overrightarrow{a_k a_i} + \sum_{j \in I \setminus \{i,k\}} \lambda_j \cdot \overrightarrow{a_i a_j} \\
&= \sum_{j \in I \setminus \{i,k\}} \lambda_j \cdot \overrightarrow{a_i a_j} - \left(\sum_{j \in I \setminus \{k\}} \lambda_j\right) \cdot \overrightarrow{a_i a_k} = 0 \text{.}
\end{aligned}
</math>

Из этого следует, что <math>\forall j \in (I \setminus \{i, k\}) : \lambda_j = 0</math> и <math>\sum_{j \in I \setminus \{k\}} \lambda_j = 0</math>, поскольку набор векторов <math>\{\overrightarrow{a_i a_j}\}_{j \in I \setminus \{i\}}</math> линейно независим. Значит, <math>\forall j \in (I \setminus \{k\}) : \lambda_j = 0</math>, то есть линейная комбинация тривиальна.
}}
Эта лемма даёт возможность говорить о независимости множества точек без выделения одной из них.
{{Определение
|definition=Пусть <math>\langle A, V, (+)\rangle</math> — это аффинное пространство. Множество точек <math>\{a_i\}_{i \in I}</math> '''аффинно независимо''', если для какого-то <math>i \in I</math> множество <math>\{\overrightarrow{a_i a_j}\}_{j \in I \setminus \{i\}}</math> линейно независимо.
}}
В аффинном пространстве справедлив факт, подобный единственности разложения вектора в ЛНЗ базис в векторном пространстве.
{{Лемма
|statement=Пусть <math>\langle A, V, (+)\rangle</math> — это аффинное пространство. Пусть <math>\{a_i\}_{i=0}^n</math> — множество точек из <math>A</math>. Пусть <math>x \in A</math> представима в виде аффинной комбинации <math>\{a_i\}_{i=0}^n</math>. Тогда набор коэффициентов аффинной комбинации <math>\{\lambda_i\}_{i=0}^n</math>, что <math>x = \sum_{i=0}^n \lambda a_i</math>, единственен тогда и только тогда, когда набор векторов <math>\{\overrightarrow{a_0 a_i}\}_{i=1}^n</math> линейно независим.
|proof=Пусть есть две аффинные комбинации с коэффициентами <math>\{\alpha_i\}_{i=0}^n</math> и <math>\{\beta\}_{i=0}^n</math>, дающие x. Посчитаем их, взяв за точку начала отсчёта точку <math>a_0</math>:

<math>\displaystyle
x
= a_0 + \sum_{i=1}^n \alpha_i \cdot \overrightarrow{a_0 a_i}
= a_0 + \sum_{i=1}^n \beta_i \cdot \overrightarrow{a_0 a_i}</math>.

Получаем, что

<math>\displaystyle
\sum_{i=1}^n \alpha_i \cdot \overrightarrow{a_0 a_i}
= \sum_{i=1}^n \beta_i \cdot \overrightarrow{a_0 a_i}</math>.

По [[#vectorUniqueness|лемме для векторного пространства]] такое разложение единственно, <math>\forall i \in \left[1..n\right] : \alpha_i = \beta_i \implies \alpha_0 = \beta_0</math>.
}}
Имеет смысл определить понятие базиса в аффинном пространстве.
{{Определение
|definition=Пусть <math>\langle A, V, (+)\rangle</math> — это аффинное пространство. Множество точек <math>\{a_i\}_{i \in I}</math> будет называться '''аффинным базисом''' этого пространства, если множество векторов <math>\{\overrightarrow{a_0 a_i}\}_{i=1}^n</math> будет базисом <math>V</math>. '''Барицентрическими координатами''' точки будут коэффициенты её аффинного разложения в этом базисе.
}}
Поскольку <math>\forall x \in A : x = a_0 + \overrightarrow{a_0 x}</math>, то если множество <math>\{\overrightarrow{a_0 a_i}\}_{i=1}^n</math> ЛНЗ, то существует единственное разложение

<math> \displaystyle
x = a_0 + \sum_{i=1}^n \lambda_i \cdot \overrightarrow{a_0 a_i}
</math>.

Тогда

<math> \displaystyle
x = \left(1 - \sum_{i=0}^n \lambda_i \right) a_0 + \sum_{i=1}^n \lambda_i a_i
</math>,

значит, разложение в аффинный базис всегда существует, и, по лемме, оно единственно.

Также можно выделить <math>a_0</math> как начало координат, и представлять координаты так же, как это делается в векторном пространстве.
Обычно так и делается.
Осознание глубинного смысла сего действия остаётся читателям в качестве упражнения.

==Вычисление поворота==
===Матрица поворота===
У нас есть гиперплоскость <tex>g</tex> и точки задающие её. В <tex>d</tex> мерном пространстве у нас будет <tex>d</tex> аффинно независимых точек <tex>a_1, a_2, \dots, a_d</tex>.

Возьмем в нашем пространстве еще одну выделенную точку <tex>p</tex>. Если она не лежит в гиперплоскости, то получившийся набор <tex>a_1, a_2, \dots, a_d, p</tex> тоже будет аффинно независимым.

[[Файл:drawing-3.png|400px|thumb|right|Пример для <tex>\mathbb{R}^3</tex>]]
Пусть у нас есть какая-то выделенная заранее система координат <tex>C</tex>. Эта система приходит обычно вместе с какой-то задачей, и обычно она декартова. И у нас тоже будет сейчас декартова.

Мы знаем, что можно составить матрицу перехода из начальной системы координат координат <tex>C</tex> в систему координат на векторах <math>\{\overrightarrow{p a_i}\}_{i=1}^d</math>, если можно выразить эти вектора в <math>C</math>.
А в нашем случае мы это сделать, конечно, можем: поскольку вектор существует между любыми парами точек, просто сопоставим нашим точкам вектора, соединяющие начало координат <tex>O</tex> и очередную точку.
Значит, если нам известны координаты точек, то нам известны координаты векторов в ситеме <tex>C</tex>.
Запишем матрицу перехода и немножко преобразуем её определитель:

<tex>\det A^ \mathrm{T}
= \begin{vmatrix}
\overrightarrow{Oa_1} - \overrightarrow{Op} \\
\overrightarrow{Oa_2} - \overrightarrow{Op} \\
\vdots \\
\overrightarrow{Oa_d} - \overrightarrow{Op}
\end{vmatrix}
= \begin{vmatrix} a_1 - p \\ a_2 - p\\ \vdots \\ a_d - p \end{vmatrix}
= \begin{vmatrix} a_1 & 1 \\ a_2 & 1\\ \vdots & \vdots \\ a_d & 1 \\ p & 1 \end{vmatrix}</tex>.

В дальнейшем нас будут интересовать знак этого детерминанта.

===Обоснование===
{{Лемма
|id=pOnPlane
|about=1
|statement=Точка <tex>p</tex> лежит на плоскости <tex>g</tex> тогда и только тогда, когда определитель матрицы <tex>A</tex> равен <tex>0</tex>.
|proof=
Плоскость <tex>g</tex> определяется замыканием набора <tex>a_1, a_2, \dots, a_d</tex> ЛНЗ точек, значит, если <tex>p</tex> принадлежит множеству, то <tex>p</tex> является линейной комбинацией этих точек. В этом случае мы с помощью преобразований можем получить нулевую стррочку в матрице <tex>A</tex>, значит, ее определитель будет ноль.
}}
Разобъем все точки пространства (кроме тех, что лежат на плоскости) на два множества в зависимости от того, какой знак для них будет иметь детерминант <tex>A</tex>. Покажем, что наша классификация осмысленна.
{{Лемма
|id= pConvex
|statement= Получившиеся множества будут выпуклыми.
|proof= По определению выпуклого множества. Возьмем две любые точки <tex>p_1</tex> и <tex>p_2</tex>, лежащие в одной области. По аксиоматике существует вектор <tex>\overrightarrow{p_1p_2}</tex> и по определению можно сделать линейную комбинацию. Значит можем получить любую точку между <tex>p_1</tex> и <tex>p_2</tex>, лежащую с ними на одной прямой, отложив от <tex>p_1</tex> вектор <tex>\alpha \cdot \overrightarrow{p_1p_2}</tex>, где <tex>\alpha \in [0..1]</tex>. Если подставить это в определитель, и вспомнить, что <math>1 = \alpha + (1 - \alpha)</math>, то получим

<tex>\begin{vmatrix} a_1 & 1 \\ a_2 & 1\\ \vdots & \vdots \\ a_d & 1 \\ p_1 + \alpha \cdot \overrightarrow{p_1p_2} & 1 \end{vmatrix} =
\begin{vmatrix} a_1 & 1 \\ a_2 & 1\\ \vdots & \vdots \\ a_d & 1 \\ \alpha p_2 + (1 - \alpha)p_1 & 1 \end{vmatrix} =
\alpha \begin{vmatrix} a_1 & 1 \\ a_2 & 1\\ \vdots & \vdots \\ a_d & 1 \\ p_2 & 1 \end{vmatrix} +
(1 - \alpha) \begin{vmatrix} a_1 & 1 \\ a_2 & 1\\ \vdots & \vdots \\ a_d & 1 \\ p_1 & 1 \end{vmatrix} </tex>.

Матрицы одинакового знака, и стоящие перед ними коэффициенты положительны. Значит, у нашей точки будет тот же знак определителя, что и у <tex>p_1</tex> и <tex>p_2</tex>.
}}
Хорошая лемма, пользоваться мы ей, конечно, не будем.

Проблема в том, что нужно показать, что любая непрерывная кривая не может пройти из точки одного множества в точку другого множества не пересекая плоскость.
Но для этого нам необходимо понятие непрерывности, а непрерывность связана с топологией. А у нас есть только афинное пространство, но нет топологии.

Можно было бы воспользоваться аналогом леммы Жордана о том, что любая замкнутая кривая без самопересечений делит пространство на две области, но у нас нет области, потому что понятие области связано с топологией.

В афинном пространстве можно вполне естественно ввести евклидовскую метрику: ввести скалярное произведение, а затем показать, что корень из скалярного произведения задает метрику. Тогда эта метрика будет индуцировать топологию открытыми шарами, а значит, можно будет воспользоваться аналогом теоремы Жордана.

Эта история о том, что даже когда мы притворяемся, что у нас нет метрики, мы неявно испоользуем топологию, индуцированную этой метрикой. Но, метрика, не единственна, и топология не единственна. Иногда нам достаточно топологии, которая даже может быть не индуцирована метрикой, или которая вообще не метризуема, но эта топология будет давать свойство непрерывности. Но тогда для нашей топогогии нужно будет доказывать вышеупомянутый факт (про непрерывность кривой).

Итак, поворот классифицирует точки не лежащие на плоскости и разбивает их на два выпуклых множества

==Уравнение гиперплоскости, полупространства==
Из [[#pOnPlane|леммы 1]] практически сразу получается уравнение гиперплоскости.

Пусть у нас есть <tex>n</tex> ЛНЗ точек <tex>a_1, a_2, \dots, a_n</tex> в <tex>n</tex>-мерном пространстве. Тогда гиперплоскость, проходящая через эти точки, может быть задана уравнением

<tex>\begin{vmatrix} a_1 & 1 \\ a_2 & 1\\ \vdots & \vdots \\ a_n & 1 \\ x & 1 \end{vmatrix} = 0</tex>.

При этом полупространство, лежащее ниже этой плоскости, может быть получено как

<tex>\begin{vmatrix} a_1 & 1 \\ a_2 & 1\\ \vdots & \vdots \\ a_n & 1 \\ x & 1 \end{vmatrix} < 0</tex>,

а полупространство, лежащее выше этой плоскости, имеет вид

<tex>\begin{vmatrix} a_1 & 1 \\ a_2 & 1\\ \vdots & \vdots \\ a_n & 1 \\ x & 1 \end{vmatrix} > 0</tex>.

Прямое произведение ДКА

2014-10-09T10:54:32Z

217.118.78.110:

{{Определение
|definition=
'''Прямым произведением''' двух [[Детерминированные конечные автоматы|ДКА]] <tex>A_1 = \langle \Sigma_1, Q_1, s_1, T_1, \delta_1 \rangle</tex> и <tex>A_2 = \langle \Sigma_2, Q_2, s_2, T_2, \delta_2 \rangle</tex> называется ДКА <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex>, где:
* <tex>\Sigma = \Sigma_1 \cup \Sigma_2</tex>
* <tex>Q = Q_1 \times Q_2</tex>
* <tex>s = \langle s_1, s_2 \rangle</tex>
* <tex>T = T_1 \times T_2</tex>
* <tex>\delta(\langle q_1, q_2 \rangle, c) = \langle \delta_1(q_1, c), \delta_2(q_2, c) \rangle</tex>
}}

== Пример ==
[[Файл:Multi_DKA_source.png]]

Возьмем автоматы:
* <tex>A_1 = \langle \Sigma = \lbrace 0, 1 \rbrace, Q_1 = \lbrace s_1, t_1 \rbrace, s_1, T_1 = \lbrace t_1 \rbrace, \delta_1 \rangle</tex>
* <tex>A_2 = \langle \Sigma = \lbrace 0, 1 \rbrace, Q_2 = \lbrace s_2, q_2, t_{21}, t_{22} \rbrace, s_2, T_2 = \lbrace t_{21}, t_{22} \rbrace, \delta_2 \rangle</tex>.

[[Файл:Multi_DKA_result.png]]

Автомат <tex>A = \langle \Sigma, Q, s, T, \delta \rangle</tex> будет их пересечением.

Согласно определению:
#<tex>\Sigma = \lbrace 0, 1 \rbrace</tex>
#<tex>Q = \lbrace \langle s_1, s_2 \rangle, \langle s_1, q_2 \rangle, \langle s_1, t_{21} \rangle, \langle s_1, t_{22} \rangle, \langle t_1, s_2 \rangle, \langle t_1, q_2 \rangle, \langle t_1, t_{21} \rangle, \langle t_1, t_{21} \rangle \rbrace</tex>
#<tex>s = \langle s_1, s_2 \rangle</tex>
#<tex>T = \lbrace \langle t_1, t_{21} \rangle, \langle t_1, t_{22} \rangle \rbrace</tex>
#<tex>\delta :</tex>
#*<tex>\delta(\langle s_1, s_2 \rangle, 0) = \langle \delta_1(s_1, 0), \delta_2(s_2, 0) \rangle = \langle s_1, q_2 \rangle </tex>
#*<tex>\delta(\langle s_1, s_2 \rangle, 1) = \langle \delta_1(s_1, 1), \delta_2(s_2, 1) \rangle = \langle t_1, s_2 \rangle </tex>
#*<tex>\delta(\langle s_1, q_2 \rangle, 0) = \langle \delta_1(s_1, 0), \delta_2(q_2, 0) \rangle = \langle s_1, q_2 \rangle </tex>
#*<tex>\delta(\langle s_1, q_2 \rangle, 1) = \langle \delta_1(s_1, 1), \delta_2(q_2, 1) \rangle = \langle t_1, t_{21} \rangle </tex>
#*...

== Применение ==
Изменив конструкцию, можно получить автомат, допускающий разность или объединение двух языков.
=== Объединение ДКА ===
[[Файл:Multi_DKA_united.png]]

Необходимо разрешать любую цепочку, удовлетворяющую первому или второму автомату, для этого сделаем терминальными следующие вершины <tex>T = (T_1 \times Q_2) \cup (Q_1 \times T_2)</tex>. Полученный автомат удовлетворяет нашим требованиям, так как попав в какое-либо состояние из <tex>T_1</tex> или <tex>T_2</tex>, цепочка будет удовлетворять первому или второму автомату соответственно.

=== Разность ДКА ===
[[Файл:Multi_DKA_division.png]]

Рассмотрим автомат <tex>\overline{M} = \langle \Sigma , Q , s , Q \setminus T , \delta \rangle </tex>, то есть автомат <tex>M</tex>, в котором терминальные и нетерминальные состояния инвертированы, если в автомате было опущено «дьявольское состояние», его необходимо добавить и сделать терминальным. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>M</tex>, а значит, задаёт язык <tex>\overline{M}</tex>.

Заметим, что если <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то <tex>L \setminus M = L \cap \overline{M}</tex> {{---}} так же регулярный.

Следовательно, надо построить пересечение двух автоматов, предварительно инвертировав во втором терминальные и нетерминальные состояния. Заметим, что меняется только набор терминальных вершин, следовательно в итоговой конструкции произведения ДКА сделаем терминальными следующие вершины <tex>T = T_1 \times (Q_2 \setminus T_2)</tex>.

== См. также ==
* [[Детерминированные конечные автоматы]]
* [[Замкнутость регулярных языков относительно различных операций]]

== Источники информации ==
* [[wikipedia:Deterministic_finite_automaton | Wikipedia {{---}} Deterministic finite automaton]]
* [http://www.andrew.cmu.edu/user/ko/pdfs/lecture-3.pdf Lecture "Formal languages, automata and computation" : Carnegie Mellon University in Qatar]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.:Издательский дом «Вильямс», 2002. {{---}} С. 152-154.

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

QpmtnCmax

2012-06-23T13:38:32Z

217.118.78.110: /* Доказательство корректности алгоритма */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==
Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеия:<tex> p_1 \ge p_2 \ge p_3... </tex>.

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> p_i</tex> - стоимость <tex>i</tex>-ой работы ;<tex> s_j</tex> - скорость работы <tex> j </tex>-oй машины ;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Кроме того, должно выполняться условие <tex>P_j/S_j \le T</tex> для всех <tex> j = 1..m - 1 </tex>, так как это нижняя оценка времени выполнения работ <tex> J_1...J_{m-1}</tex>. Исходя из этого получаем нижнюю границу <tex>C_{max}</tex> :

<tex>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>

Будем назвать <tex>Level</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>Level</tex>-алгоритма.

<tex>Level</tex> - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным <tex>level</tex>
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>находим следующую выполненную работу,где <tex> s</tex> - время ее окончания <tex> ) </tex>
<tex>t2 \leftarrow </tex> найти минимальное <tex>s > t</tex>. Для которого выполняется для некоторых работ <tex>i</tex> , <tex>j</tex>:<tex> level_i(t)>level_j(t)</tex> и <tex> level_i(s) == level_j(s)</tex>
<tex> t \leftarrow min(t1,t2) </tex> //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J </tex> - множество работ с положительным <tex>level</tex>
<tex>M = \{M_1,...,M_m\}</tex> - множество всех станков
'''WHILE''' множества <tex>J</tex> и <tex>M</tex> не пустые
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,<tex>level</tex> которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из множества <tex>I</tex> на <tex>r</tex> самых быстрых машин из множества <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==
Так как нижняя граница <tex>C_{max}</tex>:

<tex>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>

то достаточно показать, что составленное расписание достигает этой оценки.

Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <tex> p_1(0) \ge p_2(0) \ge ... \ge p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \ge p_2(t) \ge ... \ge p_n(t) </tex>. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени <tex>T</tex> нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем:

<tex> T(s_1 + ... + s_m) = p_1 + p_2 + ... + p_n </tex> или <tex> T = {P_n \over S_m} </tex>

Таким образом необходимая оценка достигается нашим алгоритмом.

Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, мы имеем следующее неравенство для времен окончания работ (обозначим далее как <tex> f_i </tex>) на станках <tex>M_1 ... M_m</tex>:

<tex> f_1 \ge f_2 \ge ... \ge f_m </tex>

В этом случае, если <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \le i \le m-1 </tex>, <tex>Level</tex> последней работы выполнявшейся на станке <tex> M_i </tex> равен <tex> f_i - \varepsilon </tex> (где <tex> \varepsilon > 0</tex> достаточно мал), и меньше чем <tex>Level</tex> последней работы на станке <tex> M_{i+1} </tex>. Пришли к противоречию.

Пусть <tex> T </tex> = <tex> f_1 = f_2 = f_3 = ... = f_j > f_{j+1}</tex> ,где <tex> j < m </tex>. Чтобы работы завершились в момент времени <tex> T </tex> необходимо начать их в момент времени 0. Так как если это не выполняется, то у нас найдется работа <tex> J_i </tex> , которая начинается позже <tex> t = 0 </tex> и заканчивается в <tex> T </tex>. Это означает что в момент времени ноль, начинаются как минимум <tex> m </tex> работ. Пусть первые <tex> m </tex> работ, стартовали вместе на всех машинах. Мы получаем <tex> p_1(0) \ge p_2(0) \ge ... \ge p_m(0) \ge p_i(0) </tex>. Из чего следует, что <tex> p_1(T - \varepsilon) \ge ... \ge p_m(T - \varepsilon) \ge p_i(T - \varepsilon) > 0 </tex> для любого <tex> \varepsilon </tex> удовлетворяющего условию <tex> 0 \le \varepsilon < T - t </tex>. Таким образом, до момента времени <tex> T </tex> нет простаивающих машин. Противоречие. Получаем <tex> T = {P_j \over S_j} </tex>.

==Пример==
[[Файл:Qpmtncmax.png|600px|thumb|right|Картинка к примеру]]

Пусть у нас есть 6 работ и 3 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_3</tex> на станках <tex>M_1-M_3</tex> соответственно. В момент времени <tex>T_1</tex> <tex>lvl</tex> 1-ой работы и 2-ой работы совпадает. С этого момента начинаем обрабатывать работы <tex> J_1,J_2</tex> синхронно на станках: <tex>M_1 M_2</tex>. В момент времени <tex>T_2</tex> работа <tex>J_3</tex> опускается до уровня работы <tex>J_4</tex>.Работы <tex> J_3,J_4</tex> выполняем одновременно на одном станке <tex> M_3</tex>. В момент времени <tex>T_3</tex> начинаем выполнять первые четыре работы на всех станках одновременно, далее просто добавятся работы <tex>J_5 J_6</tex> и все работы закончатся одновременно.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

QpmtnCmax

2012-06-23T13:00:09Z

217.118.78.110: /* Алгоритм построения расписания */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==
Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеия:<tex> p_1 \ge p_2 \ge p_3... </tex>.

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> p_i</tex> - стоимость <tex>i</tex>-ой работы ;<tex> s_j</tex> - скорость работы <tex> j </tex>-oй машины ;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Кроме того, должно выполняться условие <tex>P_j/S_j \le T</tex> для всех <tex> j = 1..m - 1 </tex>, так как это нижняя оценка времени выполнения работ <tex> J_1...J_{m-1}</tex>. Исходя из этого получаем нижнюю границу <tex>C_{max}</tex> :

<tex>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>

Будем назвать <tex>Level</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>Level</tex>-алгоритма.

<tex>Level</tex> - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным <tex>level</tex>
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>находим следующую выполненную работу,где <tex> s</tex> - время ее окончания <tex> ) </tex>
<tex>t2 \leftarrow </tex> найти минимальное <tex>s > t</tex>. Для которого выполняется для некоторых работ <tex>i</tex> , <tex>j</tex>:<tex> level_i(t)>level_j(t)</tex> и <tex> level_i(s) == level_j(s)</tex>
<tex> t \leftarrow min(t1,t2) </tex> //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J </tex> - множество работ с положительным <tex>level</tex>
<tex>M = \{M_1,...,M_m\}</tex> - множество всех станков
'''WHILE''' множества <tex>J</tex> и <tex>M</tex> не пустые
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,<tex>level</tex> которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из множества <tex>I</tex> на <tex>r</tex> самых быстрых машин из множества <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==
Так как нижняя граница <tex>C_{max}</tex>:

<tex>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>

то достаточно показать, что составленное расписание достигает этой оценки.

Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <tex> p_1(0) \ge p_2(0) \ge ... \ge p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \ge p_2(t) \ge ... \ge p_n(t) </tex>. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени <tex>T</tex> нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем:

<tex> T(s_1 + ... + s_m) = p_1 + p_2 + ... + p_n </tex> или <tex> T = {P_n \over S_m} </tex>

Таким образом необходимая оценка достигается нашим алгоритмом.

Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, мы имеем следующее неравенство для времен окончания работ (обозначим далее как <tex> f_i </tex>) на станках <tex>M_1 ... M_m</tex>:

<tex> f_1 \ge f_2 \ge ... \ge f_m </tex>

В этом случае, если <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \le i \le m-1 </tex>, Level последней работы выполнявшейся на станке <tex> M_i </tex> равен <tex> f_i - \varepsilon </tex>. Где <tex> \varepsilon > 0</tex> достаточно мал, и меньше чем <tex>Level</tex> последней работы на станке <tex> M_{i+1} </tex>. Пришли к противоречию.

Пусть <tex> T </tex> = <tex> f_1 = f_2 = f_3 = ... = f_j > f_{j+1}</tex> ,где <tex> j < m </tex>. Чтобы работы завершились в момент времени <tex> T </tex> необходимо начать их в момент времени 0. Так как если это не выполняется, то у нас найдется работа <tex> J_i </tex> , которая начинается позже <tex> t = 0 </tex> и заканчивается в <tex> T </tex>. Это означает что в момент времени ноль, начинаются как минимум <tex> m </tex> работ. Пусть первые <tex> m </tex> работ, стартовали вместе на всех машинах. Мы получаем <tex> p_1(0) \ge p_2(0) \ge ... \ge p_m(0) \ge p_i(0) </tex>. Из чего следует, что <tex> p_1(T - \varepsilon) \ge ... \ge p_m(T - \varepsilon) \ge p_i(T - \varepsilon) > 0 </tex> для любого <tex> \varepsilon </tex> удовлетворяющего условию <tex> 0 \le \varepsilon < T - t </tex>. Таким образом, до момента времени <tex> T </tex> нет простаивающих машин. Противоречие. Получаем <tex> T = {P_j \over S_j} </tex>.

==Пример==
[[Файл:Qpmtncmax.png|600px|thumb|right|Картинка к примеру]]

Пусть у нас есть 6 работ и 3 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_3</tex> на станках <tex>M_1-M_3</tex> соответственно. В момент времени <tex>T_1</tex> <tex>lvl</tex> 1-ой работы и 2-ой работы совпадает. С этого момента начинаем обрабатывать работы <tex> J_1,J_2</tex> синхронно на станках: <tex>M_1 M_2</tex>. В момент времени <tex>T_2</tex> работа <tex>J_3</tex> опускается до уровня работы <tex>J_4</tex>.Работы <tex> J_3,J_4</tex> выполняем одновременно на одном станке <tex> M_3</tex>. В момент времени <tex>T_3</tex> начинаем выполнять первые четыре работы на всех станках одновременно, далее просто добавятся работы <tex>J_5 J_6</tex> и все работы закончатся одновременно.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

Теорема Бейкера — Гилла — Соловэя

2012-05-23T21:13:25Z

217.118.78.110:

==Теорема==
{{ Теорема
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
| proof =
'''Существование оракула <tex>A</tex>'''

Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>\mathrm{TQBF}</tex>]].

<tex>
\mathrm{P^{TQBF}} \overset{(1)}{\subseteq}
\mathrm{NP^{TQBF}} \overset{(2)}{\subseteq}
\mathrm{NPS^{TQBF}} \overset{(3)}{=}
\mathrm{PS^{TQBF}} \overset{(4)}{=}
\mathrm{PS} \overset{(5)}{\subseteq}
\mathrm{P^{TQBF}}
\Rightarrow
</tex><br/>
<tex>\Rightarrow \mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>.

# <tex> \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} </tex>.
# <tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} </tex>.
# По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>.
# <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>.
# <tex> \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>.

----

'''Существование оракула <tex>B</tex>'''

Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n | \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow U_B \in \mathrm{NP^B}</tex> (сертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P^B}</tex>.

Пронумеруем некоторым образом все машины Тьюринга, имеющие доступ к оракулу языка <tex>B</tex>, и рассмотрим получившуюся последовательность <tex>M_i</tex>. Построение множества <tex>B</tex> разделим на счетное число стадий, на каждой из которых множество пополнится конечным числом элементов. Будем строить <tex>B</tex> так, чтобы на <tex>i</tex>-й стадии было выполнено: <tex>M_i</tex> не разрешает язык <tex>U_B</tex> за время не большее, чем <tex>2^{n-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}</tex>.
* 0-я стадия: <tex>B \leftarrow \emptyset </tex>.
* <tex>i</tex>-я стадия. Стадии с 0-й по <tex>(i-1)</tex>-ю пройдены, <tex>B</tex> — конечное множество слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^{n-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</tex> следующим образом:
** если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на одной из предудщих стадий, то она сохраняется;
** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.

Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^{n-1}</tex> шагов и вернуть какое-либо значение. Так как <tex>B</tex> строится с условием <tex>M_i</tex> не разрешает <tex>U_B</tex> за время <tex>2^{n-1}</tex>, то решение машины о принадлежности слова должно быть неверным:
* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <tex>\{0,1\}^n</tex>;
* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Добавим <tex>x</tex> в <tex>B</tex>. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу (то есть определить принадлежность <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>), а всего слов длины n <tex>2^n</tex>.

Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов.

Из построения получаем, что никакая машина не может разрешить <tex>U_B</tex> за время <tex>2^{n-1}</tex>. Следовательно, <tex>U_B \not\in \mathrm{P_B}</tex>.

}}

==Следствия==

{{ Утверждение
| statement = Методом диагонализации нельзя доказать, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>.
}}

{{ Утверждение
| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно "релятивизоваться", поэтому стандартные техники, например, диагонализация не применима.
}}

Теорема Бейкера — Гилла — Соловэя

2012-05-23T20:03:28Z

217.118.78.110: /* Теорема */

==Теорема==
{{ Теорема
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
| proof =
'''Существование оракула <tex>A</tex>'''

Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>\mathrm{TQBF}</tex>]].

<tex>
\mathrm{P^{TQBF}} \overset{(1)}{\subseteq}
\mathrm{NP^{TQBF}} \overset{(2)}{\subseteq}
\mathrm{NPS^{TQBF}} \overset{(3)}{=}
\mathrm{PS^{TQBF}} \overset{(4)}{=}
\mathrm{PS} \overset{(5)}{\subseteq}
\mathrm{P^{TQBF}}
\Rightarrow
</tex><br/>
<tex>\Rightarrow \mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>.

# <tex> \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} </tex>.
# <tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} </tex>.
# По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>.
# <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>.
# <tex> \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>.

----

'''Существование оракула <tex>B</tex>'''

Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n | \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow U_B \in \mathrm{NP^B}</tex> (сертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P^B}</tex>.

Пронумеруем некоторым образом все машины Тьюринга, имеющие доступ к оракулу языка <tex>B</tex>, и рассмотрим получившуюся последовательность <tex>M_i</tex>. Построение множества <tex>B</tex> разделим на счетное число стадий, на каждой из которых множество пополнится конечным числом элементов. Будем строить <tex>B</tex> так, чтобы на <tex>i</tex>-й стадии было выполнено: <tex>M_i</tex> не разрешает язык <tex>U_B</tex> за время не большее, чем <tex>2^{n-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}</tex>.
* 0-я стадия: <tex>B \leftarrow \emptyset </tex>.
* <tex>i</tex>-я стадия. Стадии с 0-й по <tex>(i-1)</tex>-ю пройдены, <tex>B</tex> — конечное множество слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^{n-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</tex> следующим образом:
** если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на одной из предудщих стадий, то она сохраняется;
** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.

Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^{n-1}</tex> шагов и вернуть какое-либо значение. Так как <tex>B</tex> строится с условием <tex>M_i</tex> не разрешает <tex>U_B</tex> за время <tex>2^{n-1}</tex>, то решение машины о принадлежности слова должно быть неверным:
* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <tex>\{0,1\}^n</tex>;
* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Добавим <tex>x</tex> в <tex>B</tex>. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу (то есть определить принадлежность <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>), а всего слов длины n <tex>2^n</tex>.

Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов.

Из построения получаем, что никакая машина не может разрешить <tex>U_B</tex> за время <tex>2^{n-1}</tex>. Следовательно, <tex>U_B \not\in \mathrm{P_B}</tex>.

}}

==Следствия==

{{ Утверждение
| statement = Методом диагонализации нельзя доказать, что <tex>\mathrm{P} \neq \mathrm{NP}</tex>.
}}

{{ Утверждение
| statement = Никакой метод, который использует операции релятивизации, не может сказать равны ли <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex>.
}}