Участник:Павел Дидин/задача о модификации 3-КНФ — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<latex> Останется ли $3-SAT$ полной, если ограничиться формулами, в которых каждая переменная…»)
 
 
Строка 2: Строка 2:
  
 
Останется ли $3-SAT$ полной, если ограничиться формулами, в которых каждая переменная входит не более $3$ раз, а каждый литерал~---~не более $2$ раз?
 
Останется ли $3-SAT$ полной, если ограничиться формулами, в которых каждая переменная входит не более $3$ раз, а каждый литерал~---~не более $2$ раз?
 +
 +
а) Под $3-SAT$ понимается НЕ-БОЛЕЕ-$3-SAT$.
 +
 +
б) Покажите, что если имеется в виду РОВНО-$3-SAT$, то не бывает невыполнимых формул указанного вида.
  
 
</latex>
 
</latex>
  
 
[[Категория:Предложенные студентами задачи]]
 
[[Категория:Предложенные студентами задачи]]

Текущая версия на 02:14, 6 марта 2021