Еженедельный по «сложности алгоритмов» для 3 курса ИСПРАН — вопросы

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?

Выберите верное утверждение

Предположим, разумеется, что Тогда что будет верно?

Является ли разрешимым множество натуральных чисел, не превосходящих :

Рассмотрим две задачи разрешения, P1 и P2, такие что

• P1 сводится полиномиально по Карпу к 3SAT
• 3SAT сводится полиномиально по Карпу к P2

Что можно утверждать?

Выберите корректное утверждение:

Является ли конкатенация двух разрешимых языков перечислимой?

Существует ли биекция между классами и ?

Пусть задача A — «есть ли цикл в ненаправленном графе». Рассмотрим набор утверждений.

• (1) Задача A — в P
• (2) Задача A — в NP
• (3) Если задача A — NP-полна, то существует НМТ, решающая A за полиномиальное время.

Что верно?

Цикл, проходящий через все вершины графа, называется