Если задача П сводится по Тьюрингу к оптимизационной, то задача П является

Если существует NP-полная задача П₁, которая сводится по Тьюрингу к задаче П₂, то задача П₂ является

Если задача П₁ сводится по Тьюрингу к задаче П₂ из класса NP, то задача П₁ является

Задача является NP-полной в сильном смысле, если

Задача с числовыми параметрами - это задача, в которой

Задача многопроцессорного расписания является

Оптимизационная задача о вершинном покрытии является

Любая NP-полная задача без числовых параметров является

Является ли задача выполнимости в нормальной конъюнктивной форме NP-полной?

Задача выполнимости булевых формул в k-конъюнктивной нормальной форме является NP-полной при значении k

Если в задаче нет полинома длины, который сверху ограничивал функцию максимума, то такая задача называется