NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиноминальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных). Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
Q844718
теории алгоритмов
Concept
Q3262192
задача с ответом «да» или «нет»
Concept
Q628036
класса NP
MISC
Q846354
полиноминальное время
MISC
Q215206
NP-полная задача
MISC
part of
part of