Алгоритм, вычислительная сложность которого ограничена сверху полиномом от функции длины и функции максимума, носит название
Если количество операций и длины слов алгоритма ограничиваются полиномом от функции длины и функции максимума, то такой алгоритм будет
Если в индивидуальной задаче нет чисел, то функция максимума для каждой задачи полагается равной
Если существует NP-полная задача П1, которая сводится по Тьюрингу к задаче П2, то задача П2 является
Если существует пара (ленточный символ - состояние), для которой существует две и более команд, такая машина Тьюринга называется
Если задача П1 сводится по Тьюрингу к задаче П2 из класса NP, то задача П1 является
Если задача П сводится по Тьюрингу к оптимизационной, то задача П является
Если числа, которые присутствуют в формулировке задачи, равномерно ограничены сверху константой, то на данном подмножестве индивидуальных задач псевдополиномиальный алгоритм становится
Задача является NP-полной в сильном смысле, если
Задача с числовыми параметрами - это задача, в которой
