База ответов ИНТУИТ

Алгоритмы и модели вычислений

<<- Назад к вопросам

Сложность функции в классе P, вычисляемой некоторой машиной Тьюринга, зависит

(Отметьте один правильный вариант ответа.)

Варианты ответа
от длины слова(Верный ответ)
от модуля считывания
от типа алфавита
Похожие вопросы
Если язык распознаваем некоторой полиномиальной машиной Тьюринга, то он называется
Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP
Если задача лежит одновременно в классе NP и в классе co-NP, то она лежит
Имитация других исполнителей машиной Тьюринга осуществляется с помощью заданий
Многопроцессорный алгоритм определения максимального элемента n-мерного массива для n2 процессоров имеет вычислительную сложность
Какова вычислительная сложность многопроцессорного алгоритма определения максимального элемента n-мерного массива для n процессоров?
Чему равны общие затраты в однопроцессорном алгоритме определения порядковых номеров в списке, если вычислительная сложность определяеся величиной O(n)?
Если классы P и NP равны, то любую задачу из класса NP можно будет решить
Если задача П1 сводится по Тьюрингу к задаче П2 из класса NP, то задача П1 является
Полином, ограничивающий вычислительную сложность псевдополиномиального алгоритма, зависит