Задача из класса NP, к которой можно свести любую другую задачу из класса NP, называется

Если классы P и NP равны, то любую задачу из класса NP можно будет решить

Если задача П₁ сводится по Тьюрингу к задаче П₂ из класса NP, то задача П₁ является

Если существует NP-полная задача П₁, которая сводится по Тьюрингу к задаче П₂, то задача П₂ является

К подклассам эквивалентности класса NP следует отнести

Языки, для которых существуют распознающие их предикаты класса P, следует отнести

Всякую задачу, принадлежащую NP, можно решить

Если NP не равно co-NP, то любая задача, которая лежит и в классе NP и в классе co-NP

Определите время, за которое можно сделать двусторонний список из одностороннего, имея процессоров, в logn раз меньше, чем n?

Если задача лежит одновременно в классе NP и в классе co-NP, то она лежит

Задача с числовыми параметрами - это задача, в которой