NP-задачи

Что значит NP в информатике?

• Non-Polynomial

• Non-Predictable

• Non-Parallel

• Non-Programmable

Какая разница между задачами P и NP?

• P может быть решена за полиномиальное время, а NP - нет

• Задачи P проще, чем NP

• NP может быть решена за полиномиальная время, а P - нет

• Нет разницы

Как можно решить оптимально NP задачу в общем случае?

• Перебирать все варианты и проверять их

• Используя жадный алгоритм

• Используя динамический алгоритм

• Она не разрешима

Какая задача относится к NP-полным?

• Сортировка

• Кратчайший путь в графе

• Коммивояжера

• Подсчет факториала

Пусть S - NP-полная задача, а Q и R - две другие задачи, о которых неизвестно, что они находятся в NP. Q - за полиномиальное время приводится к S, а S - за полиномиальное время приводится к R. Какое из следующих утверждений верно?

• R - NP-полная

• R - NP задача

• Q - NP-полная

• Q - NP задача

Пусть X - задача, относящаяся к классу NP. Тогда что из следующего верно?

• Для X не существует алгоритма за полиномиальное времени

• Если X может быть решено детерминированно за полиномиальное время, то P = NP

• X - NP-полная, если она сводится к другим задачам

• X - не имеет решения

• Все не верно

Проблема 3-SAT и 2-SAT вычислимости:

• Обе полиномиальны

• Обе NP-полные

• NP-полная и полиномиальная соответственно

• Невычислимая и NP-полная соответственно

Какое утверждение истинно?

• Существование цикла в графе определяется за полиномиальное время

• Существование цикла в графе - это NP задача

• NP-полная задача решается за полиномиальное время недетерменированным числом шагов

• Все истинно

Предположим, обнаружен алгоритм решающий задачу о клике за полиномиальное время. Какая конфигурация на картинке будет справедлива?

• A

• B

• C

• D

Пусть задача А сводится к задаче о рюкзаке, а рюкзак сводится к B. Что истина?

• A - NP, а B - NP-полная

• A - NP, а B - NP-полная, только если сведение полиномиально по времени

• B - NP, а A - NP-полная

• B - NP, а A - NP-полная, только если сведение полиномиально по времени