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

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

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

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

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

Джерела
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.