MAX-SAT: вероятностное округление/Задачи/MAX-SAT-random-t-samples — различия между версиями

Текущая версия на 08:23, 20 декабря 2016

Рассмотрим следующий алгоритм для задачи MAX-SAT.

t раз, случайно (равномерное распределение) выбираем набор — значения переменных

Какова вероятность, что будет выполнено более половины скобок?

Версия 09:53, 26 февраля 2015 (просмотреть исходный код) StasFomin (обсуждение \| вклад) (Массовая правка: замена Category:Решенные задачи на Category:Нерешенные задачи) ← Предыдущая правка		Текущая версия на 08:23, 20 декабря 2016 (просмотреть исходный код) StasFomin (обсуждение \| вклад)
(не показана одна промежуточная версия этого же участника)
Строка 7:		Строка 7:
	Какова вероятность, что будет выполнено более половины скобок?		Какова вероятность, что будет выполнено более половины скобок?

−	[[~~Category~~:~~Нерешенные~~ задачи]]	+	[[Категория:Проблемные задачи]]