NE (сложность)

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

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

В этом разделе есть несколько проблем. Помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти сообщения ) В этом разделе не указаны какие-либо источники .Пожалуйста, помогите улучшить этот раздел , добавив ссылки на надежные источники . Материалы без ссылок могут быть оспорены и удалены . ( Февраль 2023 )( Узнайте, как и когда удалить это сообщение ) Этот раздел нуждается в расширении . Вы можете помочь, дополнив его. ( Февраль 2023 ) ( Узнайте, как и когда удалить это сообщение )

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

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