Hardprob/Maximum Weighted Satisfiability With Bound — различия между версиями

Текущая версия на 22:05, 17 апреля 2023

Набор булевых переменных U, булевое выражение F над U, неотрицательное число-ограничение B ∈ N,
- для каждой переменной u ∈ U, задан вес , такой что .
Найти значения переменных для U, т.е. выбор подмножества U'⊆ U переменных которых выставили в «истину», а остальные U-U' соответственно выставлены в «ложь». Значение решения R будет
- либо B, если F ложно
- либо , если F истинно.
Максимизировать R.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <m>B∈  N</m>,
+* Набор булевых переменных <em>U</em>, булевое выражение <em>F</em> над <em>U</em>, неотрицательное число-ограничение <em>B ∈ N</em>,
-** для каждой переменной <m>u∈  U</m>, задан вес <m>w(u)∈  N</m>, такой что <m>B\le\sum\limits_{u∈  U} w(u)≤2\,B</m>.
+** для каждой переменной <em>u ∈ U</em>, задан вес <m>w(u)∈  N</m>, такой что <m>B\le\sum\limits_{u∈  U} w(u)≤2\,B</m>.
 * Найти значения переменных для <em>U</em>, т.е. выбор подмножества <em>U'⊆ U</em> переменных которых выставили в «истину», а остальные <em>U-U'</em> соответственно выставлены в «ложь». Значение решения <em>R</em> будет
 ** либо <em>B</em>, если <em>F</em> ложно