SAT - История изменений

StasFomin: Содержимое страницы заменено на «#REDIRECT discopal:{{PAGENAME}}»

2011-06-13T17:26:16Z

Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»

WikiSysop: 1 версия

2008-08-04T09:55:49Z

1 версия

BenderBot: реплицировано из внутренней CustisWiki

2006-04-20T19:06:39Z

реплицировано из внутренней CustisWiki

Новая страница

[[SAT]], от ''Satisfiability'', в русскоязычной литературе — «[[Выполнимость]]».
Формулировка задачи:

Дано булевское выражение, являющееся ''коньюнктивной нормальной формой'' (КНФ):

<amsmath>
\bigwedge_{i=1}^m K_i,
</amsmath>

где ''K<sub>i</sub>'' — ''элементарные дизьюнкции'' вида

<amsmath>x_{j_1}^{\sigma_1}\lor\ldots\lor x_{j_k}^{\sigma_k}</amsmath>, <amsmath>\sigma_j\in\{0,1\}</amsmath>, <amsmath>x^1=x</amsmath> и <amsmath>x^0=(\neg x)</amsmath>.

Существует ли (булевский) набор переменных ''x<sub>j</sub>'', обращающий эту форму в «1» (т. е. в «TRUE»)?

Известно, что задача [[SAT]] — [[NPC|NP-полна]].

Известные частные случаи — задачи [[3SAT]] и [[2SAT]].

[[Category:Задачи]]
{{replicate-from-custiswiki-to-lib}}

StasFomin в 16:09, 19 апреля 2006

2006-04-19T16:09:01Z

BenderBot: реплицировано из внутренней CustisWiki

2005-12-08T04:40:44Z

реплицировано из внутренней CustisWiki

← Предыдущая	Версия 09:55, 4 августа 2008
(не показана 1 промежуточная версия 1 участника)
(нет различий)

← Предыдущая		Версия 16:09, 19 апреля 2006
Строка 1:		Строка 1:
−	[[SAT]], от ''Satisfiability'', в русскоязычной литературе — ~~«Выполнимость»~~.	+	[[SAT]], от ''Satisfiability'', в русскоязычной литературе — «[[Выполнимость]]».
	Формулировка задачи:		Формулировка задачи:

← Предыдущая		Версия 04:40, 8 декабря 2005
(не показана 1 промежуточная версия 1 участника)
Строка 1:		Строка 1:
−	[[SAT]], от ''Satisfiability'', в русскоязычной литературе — ~~«[[Выполнимость]]»~~.	+	[[SAT]], от ''Satisfiability'', в русскоязычной литературе — «Выполнимость».
	Формулировка задачи:		Формулировка задачи:

@@ Строка 1: / Строка 1: @@
-[[SAT]], от ''Satisfiability'', в русскоязычной литературе — «[[Выполнимость]]».
+#REDIRECT [[discopal:{{PAGENAME}}]]
-Формулировка задачи:
-−
-Дано булевское выражение, являющееся ''коньюнктивной нормальной формой'' (КНФ):
-−
-<amsmath>
-    \bigwedge_{i=1}^m K_i,
-</amsmath>
-−
-где ''K<sub>i</sub>'' — ''элементарные дизьюнкции'' вида
-−
-<amsmath>x_{j_1}^{\sigma_1}\lor\ldots\lor x_{j_k}^{\sigma_k}</amsmath>, <amsmath>\sigma_j\in\{0,1\}</amsmath>, <amsmath>x^1=x</amsmath> и <amsmath>x^0=(\neg x)</amsmath>.
-−
-Существует ли (булевский) набор переменных ''x<sub>j</sub>'', обращающий эту форму в «1» (т. е. в «TRUE»)?
-−
-Известно, что задача [[SAT]] — [[NPC|NP-полна]].
-−
-Известные частные случаи — задачи [[3SAT]] и [[2SAT]].
-−
-−
-[[Category:Задачи]]
-{{replicate-from-custiswiki-to-lib}}