НЭ (сложность)

В теории сложности вычислений класс сложности NE — это набор задач решения , которые могут быть решены недетерминированной машиной Тьюринга за время O ( k ^н ) для некоторого k .

NE , в отличие от аналогичного класса NEXPTIME , не является замкнутым при полиномиальном времени сокращений «многие единицы» .

Отношения с другими классами

NE содержится в NEXPTIME .

См. также

• Е (сложность)