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

Пусть S — задача из NPC, а Q и R — тоже задачи, но про них известно только, что Q — полиномиально сводиться по Карпу к S, а S — к R.

Что будет верно?

Выберите не NP-полную задачу

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

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

Что верно?

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

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

Аню и Колю попросили показать, что задача X — NP-полна. Аня показала полиномиальную сводимость по Карпу от 3SAT к X, а Коля показал полиномиальную сводимость по Карпу от X к 3SAT.

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

Пересечение двух каких классов окажется пустым, если окажется, что ?

Будет ли класс -полных задач замкнутым относительно сводимости по Карпу, если окажется, что ?

Пусть X — задача из NP. Что верно?

Выберите общепринятое определение класса NPC (NP-полных задач).

тогда и только тогда, когда: