NP-складна задача

Співвідношення між класами P, NP, NP-Complete та NP-Hard у випадку вірності та хибності гіпотези P≠NP

NP-складна задача (англ. NP-hard) — задача не менш складна ніж NP-повна. Задача Π є NP-складною, якщо існує NP-повна задача Π1, що зводиться до Π.

Неформальний опис

Задача відноситься до класу NP-hard, якщо вона є NP-повною або невідомий недетермінований алгоритм, що розв'язує її за поліноміальний час, тобто взагалі не належить класу NP. У випадку вірності гіпотези P≠NP, для розв'язання NP-складної задачі не існує поліноміального алгоритму.

Джерела

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.