Ниже приведен пример 2 домашних заданий ТМ, в которых я не уверен, к какому классу сложности они подходят. Также необходимо выбрать класс сложности дополнения.Эти 2, в частности, смущают меня, потому что я получил другой ответ, поэтому я чувствую, что могу что-то упустить:
S = {: M - это TM st M (0) = принять} U = {: M - этоTM st M (0) [20000] = принять}
Возможные варианты: P, NP, coNP, EXP, Decidable, Recognizable, lang (все строки).
S: Я читаю это как «M проверяет, является ли ввод 0, если да, принимаю».Мой первый инстинкт заключается в том, что S находится в P, поскольку он просто проверяет, является ли вход 0, который является единственной операцией, поэтому я бы сказал, что это может быть решено за полиномиальное время.Кто-то еще решил, что RE для S и lang для дополнения S соответственно, что я просто не понимаю, если правильно.
U: Я читал то же самое, что и S, но работает ровно 2000 раз.Я также поместил бы это в P для U и его дополнения.Другим ответом является также Р, но я не вижу, как дополнение 2000 года имеет значение.
Спасибо за любые разъяснения.