И. Близнец (АУ)

Алгоритмы для $(n,3)$-MAX-SAT

Доклад по собственным результатам.

Приводятся полученные методом разбора случаев улучшенные оценки для $(n,3)$-MAX-SAT, одного из NP-полных вариантов задачи максимальной выполнимости, в котором каждая переменная появляется в формуле не более чем три раза.