Задача выполнимости булевых формул в k-конъюнктивной нормальной форме является NP-полной при значении k
Является ли задача выполнимости в нормальной конъюнктивной форме NP-полной?
Экземпляром задачи выполнимости является
Какие операции применяются в формулах в задаче выполнимости?
Какое количество литералов применяется в задаче 3-выполнимости?
К элементам экземпляра задачи выполнимости следует отнести
Если задача П сводится по Тьюрингу к оптимизационной, то задача П является
Задача с числовыми параметрами - это задача, в которой
Если существует NP-полная задача П1, которая сводится по Тьюрингу к задаче П2, то задача П2 является
Если задача П1 сводится по Тьюрингу к задаче П2 из класса NP, то задача П1 является
