http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=Chivilikhin.daniil&*Викиконспекты - Вклад участника [ru]2026-04-24T00:01:11ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%B2%D1%8B%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D0%BE%D0%B9_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B_%D0%B2_%D1%84%D0%BE%D1%80%D0%BC%D0%B5_3-%D0%9A%D0%9D%D0%A4&diff=239NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ2010-03-15T20:39:14Z<p>Chivilikhin.daniil: </p>
<hr />
<div>'''Теорема''' <br />
<br />
<tex>3SAT \in NPC </tex>, ''т.е. задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полна.''<br />
<br />
'''Доказательство'''<br />
<br />
Для того, чтобы доказать <tex>NP</tex>-полноту задачи, необходимо установить следующие факты:<br />
# <tex> 3SAT \in NPH </tex>;<br />
# <tex> 3SAT \in NP </tex>.<br />
<br />
Установим сначала первый факт, то есть <tex>NP</tex>-трудность <tex>3SAT</tex>.<br />
Для этого покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> сводится по Куку к <tex>3SAT</tex>.<br />
<br />
Рассмотрим один член булевой формулы в форме КНФ (скобку). В форме 3-КНФ этот член должен иметь вид <tex>(x \vee y \vee z)</tex>.<br />
Научимся приводить члены вида <tex>(x)</tex>, <tex>(x \vee y)</tex>, <tex>(x_1 \vee x_{2} \vee \ldots \vee x_{m})</tex> к нужному виду.<br />
<br />
* <tex>(x \vee y)</tex> заменим на <tex>(x \vee y \vee z) \wedge (x \vee y \vee \neg z)</tex>. Ясно, что последняя формула выполнима тогда и только тогда, когда выполнима исходная, при любых <tex>z</tex>;<br />
* <tex>(x)</tex> заменим на <tex>(x \vee y) \wedge (x \vee \neg y)</tex> - свели задачу к предыдущей;</div>Chivilikhin.daniilhttp://neerc.ifmo.ru/wiki/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%B2%D1%8B%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D0%BE%D0%B9_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B_%D0%B2_%D1%84%D0%BE%D1%80%D0%BC%D0%B5_3-%D0%9A%D0%9D%D0%A4&diff=238NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ2010-03-15T20:07:50Z<p>Chivilikhin.daniil: </p>
<hr />
<div>'''Теорема''' <br />
<br />
<tex>3SAT \in NPC </tex>, ''т.е. задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полна.''<br />
<br />
'''Доказательство'''<br />
<br />
Для того, чтобы доказать <tex>NP</tex>-полноту задачи, необходимо установить следующие факты:<br />
# <tex> 3SAT \in NPH </tex>;<br />
# <tex> 3SAT \in NP </tex>.<br />
<br />
Установим сначала первый факт, то есть <tex>NP</tex>-трудность <tex>3SAT</tex>.<br />
Для этого покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> сводится по Куку к <tex>3SAT</tex>.</div>Chivilikhin.daniilhttp://neerc.ifmo.ru/wiki/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%B2%D1%8B%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D0%BE%D0%B9_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B_%D0%B2_%D1%84%D0%BE%D1%80%D0%BC%D0%B5_3-%D0%9A%D0%9D%D0%A4&diff=237NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ2010-03-15T20:02:55Z<p>Chivilikhin.daniil: </p>
<hr />
<div>'''Теорема''' <tex>3SAT \in NPC </tex>, ''т.е. задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полна.''<br />
'''Доказательство'''<br />
Для того, чтобы доказать <tex>NP</tex>-полноту задачи, необходимо установить следующие факты:<br />
# <tex> 3SAT \in NPH </tex>;<br />
# <tex> 3SAT \in NP </tex>.</div>Chivilikhin.daniilhttp://neerc.ifmo.ru/wiki/index.php?title=NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BE_%D0%B2%D1%8B%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%B1%D1%83%D0%BB%D0%B5%D0%B2%D0%BE%D0%B9_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D1%8B_%D0%B2_%D1%84%D0%BE%D1%80%D0%BC%D0%B5_3-%D0%9A%D0%9D%D0%A4&diff=236NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ2010-03-15T19:54:10Z<p>Chivilikhin.daniil: Новая страница: «'''Теорема''' 3<tex>-SAT \in NPC </tex> (задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полн…»</p>
<hr />
<div>'''Теорема''' 3<tex>-SAT \in NPC </tex> (задача о выполнимости булевой формулы в форме 3-КНФ <tex>NP</tex>-полна)</div>Chivilikhin.daniilhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_(%D1%81%D1%82%D0%B0%D1%80%D0%B0%D1%8F_%D1%82%D1%80%D0%B5%D1%88%D0%BE%D0%B2%D0%B0%D1%8F_%D0%B2%D0%B5%D1%80%D1%81%D0%B8%D1%8F)&diff=212Теория сложности (старая трешовая версия)2010-03-15T08:13:43Z<p>Chivilikhin.daniil: </p>
<hr />
<div>== Лекция 1 ==<br />
*[[Класс DSPACE]]<br />
*[[Класс DTIME]]<br />
*[[Теорема о емкостной иерархии]]<br />
*[[Теорема о временной иерархии]]<br />
*[[Сведение по Карпу]]<br />
*[[Сведение по Куку]]<br />
<br />
== Практика 1 ==<br />
*[[Сведение по Куку задачи факторизации к языку из NP]]<br />
<br />
== Лекция 2 ==<br />
*[[Теорема Кука]]<br />
<br />
== Практика 2 ==<br />
*[[NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ]]<br />
<br />
== Лекция 3 ==<br />
*[[Теорема Ладнера]]<br />
*[[Теорема Левина]]<br />
*[[Теорема Бейкера-Гилла-Соловэя]]<br />
<br />
== Практика 3 ==<br />
*[[NP-полнота задач о гамильтоновом цикле и пути в графах]]<br />
*[[NP-полнота задачи о сумме подмножества]]<br />
*[[NP-полнота задачи о рюкзаке]]<br />
<br />
== Практика, которой на самом деле не было ==<br />
*[[NP-полнота задачи о раскраске графа]]<br />
<br />
== Лекция 4 ==<br />
*[[PS-полнота задачи Generalized geography]]</div>Chivilikhin.daniil