https://discopal.ispras.ru/index.php?action=history&feed=atom&title=Hardprob%2FMaximum_Not-All-Equal_3-Satisfiability
Hardprob/Maximum Not-All-Equal 3-Satisfiability - История изменений
2026-04-20T02:24:11Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Not-All-Equal_3-Satisfiability&diff=24782&oldid=prev
StasFomin в 06:51, 17 апреля 2023
2023-04-17T06:51:08Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 06:51, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3" >Строка 3:</td>
<td colspan="2" class="diff-lineno">Строка 3:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Коллекция <em>C</em> скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше <em>3</em>.  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Коллекция <em>C</em> скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше <em>3</em>.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти истинное присваивание для <em>U</em>, и подмножество скобок <em>C'⊆ C</em>, таких что каждая скобка имеет по крайней мере один истинный литерал и не меньше одного ложного литерала.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти истинное присваивание для <em>U</em>, и подмножество скобок <em>C'⊆ C</em>, таких что каждая скобка имеет по крайней мере один истинный литерал и не меньше одного ложного литерала.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать размер этого подмножества <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">\vert </del>C'| → <del class="diffchange diffchange-inline">\</del>max</<del class="diffchange diffchange-inline">m</del>></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать размер этого подмножества <<ins class="diffchange diffchange-inline">em</ins>><ins class="diffchange diffchange-inline">|</ins>C'| → max</<ins class="diffchange diffchange-inline">em</ins>></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Not-All-Equal_3-Satisfiability&diff=23758&oldid=prev
StasFomin: Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Множество переменных <em>U</em>, * Коллекция <em>C</em> скоб…»
2023-04-13T15:30:43Z
<p>Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Множество переменных <em>U</em>, * Коллекция <em>C</em> скоб…»</p>
<p><b>Новая страница</b></p><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --><br />
* Множество переменных <em>U</em>, <br />
* Коллекция <em>C</em> скобок-дизъюнкций литералов, где литерал это какая-то переменная или ее отрицание, размер скобки не больше <em>3</em>. <br />
* Найти истинное присваивание для <em>U</em>, и подмножество скобок <em>C'⊆ C</em>, таких что каждая скобка имеет по крайней мере один истинный литерал и не меньше одного ложного литерала.<br />
* Максимизировать размер этого подмножества <m>\vert C'| → \max</m><br />
<br />
----<br />
{{hard-problem-on-lab17|{{PAGENAME}}}}<br />
<!-- * {{has-testdata-and-visualization}} --><br />
<!-- * {{has-pyomo-model}} --><br />
<!-- * {{has-npc-reduction}} --><br />
<!-- * {{add-random-fuzzing-tests}} --><br />
----<br />
<small><br />
{{ViggoCode|node228}}<br />
{{GDCode|LO3}}<br />
<!-- * [ Задача в википедии] --><br />
</small><br />
<!-- end --><br />
<br />
[[Категория:ClassicHardProblems]]</div>
StasFomin