Редактирование: Методы оптимизации, задачи
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 30 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 55: | Строка 55: | ||
# При k = 2: | # При k = 2: | ||
- | : <math>y_1 \vee y_2 = (y_1 \vee y_2 \vee \bar{u}) \wedge (y_1 \vee | + | : <math>y_1 \vee y_2 = (y_1 \vee y_2 \vee \bar{u}) \wedge (y_1 \vee u_1 \vee u).</math> |
При этом переменные <math>u</math> являются фиктивными, то есть такая замена является эквивалентной (в отличие от замены для случая k = 3). Таким образом, эти три преобразования позволяют полиномиально свести задачу ВЫП к задаче 3-ВЫП. | При этом переменные <math>u</math> являются фиктивными, то есть такая замена является эквивалентной (в отличие от замены для случая k = 3). Таким образом, эти три преобразования позволяют полиномиально свести задачу ВЫП к задаче 3-ВЫП. | ||
+ | |||
+ | |||
== Задача 4 == | == Задача 4 == |