Про гипотезу Кука

Автор темы shestakovyi34 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеВ марте в МГУ имени М.В. Ломоносова пройдет II Кубок Москвы по Го среди студентов ВУЗов14.02.2020 11:44
06.12.2019 07:34
Про гипотезу Кука
Ой-ой-ой! Не смешите мой живот больной! Какой такой Кук? Какая такая гипотеза? Прежде, чем выдвигать гипотезу, необходимо изучить основные логические операции и правила работы с ними. Так, если в логическом выражении все переменные связаны операцией конъюнкция (И), то логическим значением выражения будет ИСТИНА, если все переменные имеют значение ИСТИНА, в противном случае – ЛОЖЬ. Если же в логическом выражении все переменные связаны операцией дизъюнкция (ИЛИ), то значением выражения будет ИСТИНА, когда хотя бы одна переменная имеет значение ИСТИНА, в противном случае – ЛОЖЬ. Поэтому, задача ВЫПОЛНИМОСТЬ решается “на раз-два”: берём любое логическое выражение и приводим его конъюнктивной нормальной форме и, в случае, когда в каждом подскобочном выражении хотя бы одна переменная имеет значение ИСТИНА, то всё выражение будет иметь значение ИСТИНА. Можно выражение привести к дизъюнктивной нормальной форме. Тогда его значением будет ИСТИНА, когда хотя бы в одном подскобочном выражении все переменные принимают значение ИСТИНА. Т.к. доказано, что к задаче ВЫПОЛНИМОСТЬ сводятся несколько сотен подобных по сложности задач, а задача ВЫПОЛНИМОСТЬ имеет полиномиальный алгоритм решения, то и для всех этих задач должны существовать подобные алгоритмы. Например, задача 3COLOR решается “на раз”: если какая-нибудь внутренняя область имеет общие границы с нечетным количеством соседних областей, то трёх красок будет недостаточно для закрашивания её и граничащий с ней областей.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти