Редактирование: Методы оптимизации, 02 лекция (от 15 февраля)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 23: | Строка 23: | ||
Утв. 3. Если П' полиномиально сводится к П и П ∈ '''P''', то П' ∈ '''P'''. | Утв. 3. Если П' полиномиально сводится к П и П ∈ '''P''', то П' ∈ '''P'''. | ||
- | Доказательство. <math>\exist A \exist p(.)</math>. Построим алгоритм A', решающий задачу П': <math>A' = A \times A_f I' \in \Pi' \overbrace{\rArr}{A_f} I \in \Pi | + | Доказательство. <math>\exist A \exist p(.)</math>. Построим алгоритм A', решающий задачу П': <math>A' = A \times A_f I' \in \Pi' \overbrace{\rArr}{A_f} I \in \Pi {overbrace}{\dArr}{A} </math> решение, <math>t_{A'}(I') \le p(P_f(|I|))</math>. |
Соврешенно аналогично получаем | Соврешенно аналогично получаем |